Skip to content

Instantly share code, notes, and snippets.

@justinHowlett
Created June 21, 2013 22:21
Show Gist options
  • Save justinHowlett/5834778 to your computer and use it in GitHub Desktop.
Save justinHowlett/5834778 to your computer and use it in GitHub Desktop.
Quick sort in Objective-C
-(void)quickSortArray:(NSMutableArray*)array fromLeftIndex:(NSUInteger)leftIndex toRightIndex:(NSUInteger)rightIndex{
NSUInteger chosenPivot = 0;
if (leftIndex == 0 && rightIndex == 0)
rightIndex = array.count - 1;
chosenPivot = leftIndex + ceil((rightIndex - leftIndex) * 0.5);
NSUInteger newPivot = [self partitionArray:array pivot:chosenPivot left:leftIndex right:rightIndex];
if (newPivot > 0){
if (leftIndex < newPivot-1 && newPivot+1 < rightIndex){
[self quickSortArray:array fromLeftIndex:leftIndex toRightIndex:newPivot-1]; //recursively sort to the left
[self quickSortArray:array fromLeftIndex:newPivot+1 toRightIndex:rightIndex]; //recursively sort to the right
}else{
NSLog(@"array is sorted %@",array);
}
}
}
-(NSUInteger)partitionArray:(NSMutableArray*)array pivot:(NSUInteger)pivotIndex left:(NSUInteger)leftmostIndex right:(NSUInteger)rightmostIndex{
NSNumber* pivotValue = array[pivotIndex];
NSUInteger storedIndex = leftmostIndex;
/** place the pivot at the rightmost index */
[self swapFirstIndex:pivotIndex withSecondIndex:rightmostIndex inMutableArray:array];
/* swap the rest at this level*/
for(int v = leftmostIndex; v < rightmostIndex; v++) {
/** compare value at index to pivot's value. If less than pivot value place at left of the pivot point and move the pivot point right one */
if([array[v]intValue] < pivotValue.intValue) {
[self swapFirstIndex:v withSecondIndex:storedIndex inMutableArray:array];
storedIndex ++;
}
}
/** return the pivot to the original position */
[self swapFirstIndex:rightmostIndex withSecondIndex:storedIndex inMutableArray:array];
/** return repositioned pivot index */
return storedIndex;
}
-(void)swapFirstIndex:(NSUInteger)firstIndex withSecondIndex:(NSUInteger)secondIndex inMutableArray:(NSMutableArray*)array{
NSNumber* valueAtFirstIndex = array[firstIndex];
NSNumber* valueAtSecondIndex = array[secondIndex];
[array replaceObjectAtIndex:firstIndex withObject:valueAtSecondIndex];
[array replaceObjectAtIndex:secondIndex withObject:valueAtFirstIndex];
}
@justinHowlett
Copy link
Author

Don't ever use this, the built in NSArray methods are much quicker and much better

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment