Last active
December 4, 2015 18:57
-
-
Save MinhasKamal/9302016 to your computer and use it in GitHub Desktop.
This is a simple implementation of quick-sort algorithm in C language.
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
100 //number of integers | |
19 34 29 67 37 90 99 89 45 56 | |
64 73 85 21 38 23 57 18 94 36 | |
67 67 45 45 78 67 65 78 56 71 | |
56 45 60 45 64 70 65 76 85 69 | |
54 50 39 45 90 69 57 65 71 65 | |
78 45 61 54 60 53 68 54 70 65 | |
79 40 56 34 58 39 59 46 43 70 | |
68 76 88 99 97 100 67 84 89 82 | |
81 79 74 12 11 15 100 99 56 34 | |
26 33 98 96 94 97 93 29 100 98 |
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
/** | |
* Developer: Minhas Kamal | |
* Date: August.2013 | |
* Comment: Sorts the containing integers of a file using Quick Sort. The file format is as follows. | |
**/ | |
///FileFormat | |
/* | |
100 //number of integers | |
19 34 29 67 37 90 99 89 45 56 | |
64 73 85 21 38 23 57 18 94 36 | |
67 67 45 45 78 67 65 78 56 71 | |
56 45 60 45 64 70 65 76 85 69 | |
54 50 39 45 90 69 57 65 71 65 | |
78 45 61 54 60 53 68 54 70 65 | |
79 40 56 34 58 39 59 46 43 70 | |
68 76 88 99 97 100 67 84 89 82 | |
81 79 74 12 11 15 100 99 56 34 | |
26 33 98 96 94 97 93 29 100 98 | |
*/ | |
#include <iostream> | |
#include <fstream> | |
using namespace std; | |
void quickSort(int *myArray, int left, int right); //sorts the list | |
int findLock(int *myArray, int left, int right); //swaps & places one element at right place | |
int main() | |
{ | |
char* inputFileName; | |
cout << "Input the file name (full path): "; | |
cin >> inputFileName; | |
ifstream list; //input file stream | |
list.open(inputFileName); | |
//list.open(argv[1]); | |
if(!list.is_open()){ //when file is not found | |
cout << "File is not found!\n"; | |
return 0; | |
} | |
int member; //number of integers | |
list >> member; | |
int myArray[member]; //stores the input data | |
for(int i=0; i<member; i++) //reading the data | |
list >> myArray[i]; | |
int left=0, right=member-1; | |
if(member>1) | |
quickSort(myArray, left, right); | |
for(int i=0; i<member; i++) //printing the data | |
cout << myArray[i] << endl; | |
list.close(); | |
return 0; | |
} | |
void quickSort(int *myArray, int left, int right) | |
{ | |
if(left<right){ | |
int loc=findLock(myArray, left, right); | |
quickSort(myArray, left, loc-1); | |
quickSort(myArray, loc+1, right); | |
} | |
return ; | |
} | |
int findLock(int *myArray, int left, int right) | |
{ | |
int lock=left; | |
while(1){ | |
while(myArray[lock]<=myArray[right] && lock!=right) //searching from right to left | |
right--; | |
if(lock==right) break; | |
if(myArray[lock]>myArray[right]){ | |
int temp=myArray[lock]; //swapping | |
myArray[lock]=myArray[right]; | |
myArray[right]=temp; | |
lock=right; | |
} | |
while(myArray[left]<=myArray[lock] && lock!=left) //searching from left to right | |
left++; | |
if(lock==left) break; | |
if(myArray[left]>myArray[lock]){ | |
int temp=myArray[lock]; //swapping | |
myArray[lock]=myArray[left]; | |
myArray[left]=temp; | |
lock=left; | |
} | |
} | |
return lock; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Give it a file; the first line should be a value telling the number of integers, the rest will be input integers.