Sorting Algorithms in Objective – C
There are a list of available sorting algorithms. Quicksort, heapsort and mergesort have better performance in comparison to insertionSort, selectionsort, bubblesort.
In this article we will visit some of the commonly known sorting algorithms and implement the same in Objective C.
It is not advisable writing your own sorting algorithms. Rather we should use the sort/compare methods available in Objective C Data structures.
This article will be continuously updated with different sorting algorithms implementation.
Bubble Sort
- A simple sorting algorithm that repeatedly steps through the list to be sorted and compares each pair of adjacent items and swaps them in the desired order.
- This is NOT efficient and not a practical sorting algorithm when n is large
- Best: n, Average:
, Worst:
//Begin test Bubble Sorting Code NSArray *dArray =@[@101, @201, @301,@121,@11,@123,@21,@14,@32,@76,@89,@987,@65]; NSMutableArray *dataArray = [NSMutableArray arrayWithArray:dArray]; //Check Bubble Sort NSArray *bubbleSortedArray = [self bubbleSort:dataArray]; NSLog(@"bubbleSortCount %d",bubbleSortCount); //Number of Iterations //bubbleSortCount is a static variable initialized to 0 //Gives the average & worst case of n^2 NSLog(@"bubbleSortedArray %@",bubbleSortedArray); //Prints the sorted array bubbleSortCount =0; //Reinitialize the static variable to 0 to retest NSLog(@"bubbleSortedArray %@",[self bubbleSort:bubbleSortedArray]); //Resort the already sorted array NSLog(@"bubbleSortCount %d",bubbleSortCount); //Gives the best case count of n //End test Bubble Sorting Code -(NSArray *)bubbleSort:(NSMutableArray *)unsortedDataArray { long count = unsortedDataArray.count; int i; bool swapped = TRUE; while (swapped){ swapped = FALSE; for (i=1; i<count;i++) { if ([unsortedDataArray objectAtIndex:(i-1)] > [unsortedDataArray objectAtIndex:i]) { [unsortedDataArray exchangeObjectAtIndex:(i-1) withObjectAtIndex:i]; swapped = TRUE; } //bubbleSortCount ++; //Increment the count everytime a switch is done, this line is not required in the production implementation. } } return unsortedDataArray; }
Bubble Sort Visualization (Click Here to Go to the Visualization – Generation Code)
Selection Sort
- Best: , Average: , Worst:
- Inefficient on large lists
- Worse performance from insertion sort
Steps
- Divide the input list into two parts, the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list.
- Initially, the sorted sublist is empty and the unsorted sublist is the entire input list.
- The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.
-(NSArray *)selectionSort:(NSMutableArray *)unsortedDataArray{
int pointerMin;
int i,j;
long count = unsortedDataArray.count;
for (j=0; j<count;j++ )
{
//for each element in the array, assume that the first element is the minimum number
pointerMin =j;
for (i=j+1;i<count;i++)
{
//Iterate through each element in the array starting from the next element and compare with minimum number set from the outer for loop
if ([unsortedDataArray objectAtIndex:i] < [unsortedDataArray objectAtIndex:pointerMin] )
{
pointerMin = i; //Change pointer to minimum number if new min found
selectionSortCount++;
}
}
if (pointerMin !=j) //if new pointer is not same as the old pointer then swap
{
[unsortedDataArray exchangeObjectAtIndex:j withObjectAtIndex:pointerMin];
}
}
return unsortedDataArray;
}
Insertion Sort
- Simple Implementation
- Efficient on smaller datasets
- more efficient than selection sort and bubble sort
- Best = n, Average = n^2, Worst = n^2
-(NSArray *)insertionSort:(NSMutableArray *)unsortedDataArray
{
long count = unsortedDataArray.count;
int i,j;
for (i=1; i<count;i++)
{
j=i;
while(j>0 && [[unsortedDataArray objectAtIndex:(j-1)] intValue] > [[unsortedDataArray objectAtIndex:j] intValue])
{
[unsortedDataArray exchangeObjectAtIndex:j withObjectAtIndex:(j-1)];
j=j-1;
insertionSortCount++;
}
}
return unsortedDataArray;
}
Quick Sort
- The quicksort algorithm divides a list/array into two smaller arrays (low elements & high elements)
- Step 1: Pick a pivot point (In this sample we have picked a random pivot point between the range of the list)
- Step 2: Divide/Reorder the list so that all the elements smaller than the pivot is added to the low elements array and all the elements greater than the pivot are added to the high element array.
- Step 3: Repeat Step 1 and Step 2 for the sub arrays/lists
- Recreate the array by joining (the lowelement array), (the pivot) and (the high element array)
- Best: n Log n, Average: n log n, Worst:n^2
-(NSArray *)quickSort:(NSMutableArray *)unsortedDataArray
{
NSMutableArray *lessArray = [[[NSMutableArray alloc] init] autorelease];
NSMutableArray *greaterArray =[[[NSMutableArray alloc] init] autorelease];
if ([unsortedDataArray count] <1)
{
return nil;
}
int randomPivotPoint = arc4random() % [unsortedDataArray count];
NSNumber *pivotValue = [unsortedDataArray objectAtIndex:randomPivotPoint];
[unsortedDataArray removeObjectAtIndex:randomPivotPoint];
for (NSNumber *num in unsortedDataArray)
{
quickSortCount++; //This is required to see how many iterations does it take to sort the array using quick sort
if (num < pivotValue)
{
[lessArray addObject:num];
}
else
{
[greaterArray addObject:num];
}
}
NSMutableArray *sortedArray = [[[NSMutableArray alloc] init] autorelease];
[sortedArray addObjectsFromArray:[self quickSort:lessArray]];
[sortedArray addObject:pivotValue];
[sortedArray addObjectsFromArray:[self quickSort:greaterArray]];
return sortedArray;
}
Merge Sort
Merge sorting is a good sorting algorithm and has consistent performance
- Divide the list into the smallest unit (1 element)
- Compare each element with the adjacent list to sort and merge the two adjacent lists
Worst case performance O(n log n)
Best case performance O(n log n)
Average case performance O(n log n)
-(NSArray *)mergeSort:(NSArray *)unsortedArray
{
if ([unsortedArray count] < 2)
{
return unsortedArray;
}
long middle = ([unsortedArray count]/2);
NSRange left = NSMakeRange(0, middle);
NSRange right = NSMakeRange(middle, ([unsortedArray count] - middle));
NSArray *rightArr = [unsortedArray subarrayWithRange:right];
NSArray *leftArr = [unsortedArray subarrayWithRange:left];
//Or iterate through the unsortedArray and create your left and right array
//for left array iteration starts at index =0 and stops at middle, for right array iteration starts at midde and end at the end of the unsorted array
NSArray *resultArray =[self merge:[self mergeSort:leftArr] andRight:[self mergeSort:rightArr]];
return resultArray;
}
-(NSArray *)merge:(NSArray *)leftArr andRight:(NSArray *)rightArr
{
NSMutableArray *result = [[NSMutableArray alloc] init];
int right = 0;
int left = 0;
while (left < [leftArr count] && right < [rightArr count])
{
if ([[leftArr objectAtIndex:left] intValue] < [[rightArr objectAtIndex:right] intValue])
{
[result addObject:[leftArr objectAtIndex:left++]];
}
else
{
[result addObject:[rightArr objectAtIndex:right++]];
}
}
NSRange leftRange = NSMakeRange(left, ([leftArr count] - left));
NSRange rightRange = NSMakeRange(right, ([rightArr count] - right));
NSArray *newRight = [rightArr subarrayWithRange:rightRange];
NSArray *newLeft = [leftArr subarrayWithRange:leftRange];
newLeft = [result arrayByAddingObjectsFromArray:newLeft];
return [newLeft arrayByAddingObjectsFromArray:newRight];
}
Generate Fibonacci Series
The following code generates the first 20 numbers in Fibonacci Series
-(void)generateFibonnaciSeries
{
NSMutableArray *mArray = [NSMutableArray new];
NSNumber *fibNum1 = [NSNumber numberWithDouble:1];
NSNumber *fibNum2 = [NSNumber numberWithDouble:1];
[mArray addObject:fibNum1];
[mArray addObject:fibNum2];
for (int i=2; i<20; i++)
{
[mArray addObject:[NSNumber numberWithDouble:[[mArray objectAtIndex:i-1] doubleValue] +[[mArray objectAtIndex:i-2] doubleValue]]];
}
NSLog(@"mArray %@",mArray);
}
Excel Header – Column alphabet sequence
NSArray *alphabetArray = @[@"A",@"B",@"C",@"D",@"E",@"F",@"G",@"H",@"I",@"J",@"K",@"L",@"M",@"N",@"O",@"P",@"Q",@"R",@"S",@"T",@"U",@"V",@"W",@"X",@"Y",@"Z"];
NSMutableArray *newAlphabetArray = [NSMutableArray new];
int endIndex = 16384;
for (int i=0; i 0 && quotient < 27)
{
alpha =[NSString stringWithFormat:@"%@%@",[alphabetArray objectAtIndex:quotient-1],[alphabetArray objectAtIndex:remainder]];
[newAlphabetArray addObject:alpha];
}
else if (quotient >26)
{
secondLevelQuotient = quotient / 26;
secondLevelRemainder = quotient % 26;
if (secondLevelRemainder == 0)
{
alpha = [NSString stringWithFormat:@"%@%@%@",[alphabetArray objectAtIndex:secondLevelQuotient-1],[alphabetArray objectAtIndex:secondLevelRemainder],[alphabetArray objectAtIndex:remainder]];
}
else
{
alpha = [NSString stringWithFormat:@"%@%@%@",[alphabetArray objectAtIndex:secondLevelQuotient-1],[alphabetArray objectAtIndex:secondLevelRemainder-1],[alphabetArray objectAtIndex:remainder]];
}
[newAlphabetArray addObject:alpha];
}
}
Is this is a bottoms-up iterative merge sort, or a hybrid can’t classify it, since the merge is embedded as part the algorithm for speed.
class cSort_t
{
public:
template
static void insertionSort (T* _array, const unsigned size);
template
static void mergeSort(T *data, const unsigned size);
protected:
cSort_t ();
~cSort_t ();
cSort_t (const cSort_t& ref);
const cSort_t& operator= (const cSort_t& ref);
private:
template
_inline static void copyElements(T * dst,T * src, unsigned size);
};
//—————– Insertion Sort ——————–
template
void cSort_t::insertionSort (T* _array, const unsigned size)
{
T _temp;
for (int unsorted = 1; unsorted=0; –index)
{
if (_temp < *(_array+index))
{
*(_array+index+1) = *(_array+index);
if (0==index)
*_array = _temp;
}
else
{
*(_array+index+1) = _temp;
break;
}
}
}
}
template
__inline void cSort_t::copyElements(T * dst, T * src, int size)
{
while(size > 3)
{
*(dst+0) = *(src+0);
*(dst+1) = *(src+1);
*(dst+2) = *(src+2);
*(dst+3) = *(src+3);
dst+=4;
src+=4;
size-=4;
};
while(size > 0)
{
*dst++ = *src++;
size–;
};
}
//—————– Merge Sort Function ———————-
// Bottom’s up iterative merge sort.
// Internal working buffer(temp[size]).
// Simple ping-pong buffering to reduce copy backs.
// Stable sort, maximum sort complexity=(n*log n).
// Faster then most sorts for general purpose use.
// Returns the sorted result in the input buffer.
template
void cSort_t::mergeSort(T *data, unsigned size)
{
// use insertion sort for sorting small arrays
if(size < 32)
{
insertionSort (data, size);
return;
}
unsigned old_size = 0;
unsigned int i,sp0c,sp1,sp1c;
T *p0,*p1,*tmp,*tp1,*tp2;
T *temp = new T [size]; // create an internal working temp
// do easy first pass of bottoms up merge sort
// make the final sorted data end up back in input array to save moves.
// by using either a in-place compare swap or a out-place compare move.
i=0; for(unsigned j=1; j<size; j <= size
if(i&1)
{
// do an in-place compare and swap
p0 = data;
for(i=1; i *(p0+1)) {*temp = *p0; *p0 = *(p0+1); *(p0+1) = *temp;}
}
tp1 = data;
tp2 = temp;
}
else
{
// do an out of place compare and move
p0 = data;
p1 = temp;
for(i=1; i<size; i+=2, p0+= 2, p1+= 2)
{
if(*p0 <= *(p0+1)) {*p1 = *p0; *(p1+1) = *(p0+1);}
else {*p1 = *(p0+1); *(p1+1) = *p0;}
}
if(size&1) *p1 = *p0; // move last "odd" word
tp1 = temp;
tp2 = data;
}
// do more complex part of the binary sort
// only complication added is handing the right side element's remainder.
p0 = tp1;
tmp = tp2;
for(i=2; i<size; i<<=1)
{
p1 = p0 + i;
sp1 = size – i;
for(;;)
{
sp0c = sp1c = i;
// last pass left and right lengths are different.
if(sp1 < i) sp1c = sp1;
for(;;)
{
if(*p0 <= *p1) // simple compare merge pass
{
*tmp++ = *p0++; // move a left side element
if((–sp0c) == 0)
{
// no more left side elements, move what's remaining of right side's elements
do *tmp++ = *p1++; while((–sp1c) != 0);
break;
}
}
else
{
*tmp++ = *p1++; // move a right side element
if((–sp1c) == 0)
{
// no more right side elements, move what's remaining of left side's elements
do *tmp++ = *p0++; while((–sp0c) != 0);
break;
}
}
}
p0 = p1; // adjust left side and right side pointers
p1 += i;
if(sp1 <= (i<<1)) break;
sp1 -= (i< i)
{
// optional test(no need to copy the same end data more than once).
if(old_size < (sp1-i))
{
old_size = (sp1-i);
copyElements(tmp, p0, (sp1-i));
}
}
// swap working pointers
p0 = tp2;
tmp = tp2 = tp1;
tp1 = p0;
}
// delete internal working temp
delete [] temp;
}
I thought this was a c++ comment area, not an objective c
sorry please delete these comments the comment parser is messing up the code so it will not work. Some comment parsers like spaces others like tabs, yours also deletes and messes up }{ and << becomes <
best sloutions for this program
http://programmergallery.com/c-program/bubble-sort-algorith-program-using-c-program.php