Created
June 21, 2013 22:21
-
-
Save justinHowlett/5834778 to your computer and use it in GitHub Desktop.
Quick sort in Objective-C
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-(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]; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Don't ever use this, the built in NSArray methods are much quicker and much better