daniel.baird
10/4/2018 - 4:33 AM

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

quickSort.m
content_copyfile_download

- (NSArray<NSNumber *> *)quickSort:(NSArray<NSNumber *> *)unsortedArray {
    if ([unsortedArray count] < 1) {
        return nil;
    }
    NSMutableArray<NSNumber *> *unsorted = [unsortedArray mutableCopy];
    NSMutableArray<NSNumber *> *smallArray = [NSMutableArray new];
    NSMutableArray<NSNumber *> *bigArray = [NSMutableArray new];
    
    // Pick a piviot point. It is just a random index in the array.
    NSInteger pivot = arc4random() % unsorted.count;
    
    // That piviot poitn is what is used to divide into large and small.
    NSNumber *pivotValue = [unsorted objectAtIndex:pivot];
    
    // Remove the pivot point from the original array. We already know where we are going to put that.
    [unsorted removeObjectAtIndex:pivot];
    for (NSNumber *num in unsorted) {
        if (num < pivotValue) {
            [smallArray addObject:num];
        } else {
            [bigArray addObject:num];
        }
    }
    
    NSMutableArray *sortedArray = [NSMutableArray new];
    [sortedArray addObjectsFromArray:[self quickSort:smallArray]];
    [sortedArray addObject:pivotValue];
    [sortedArray addObjectsFromArray:[self quickSort:bigArray]];
    return sortedArray;
}