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];
        }
    }