Skip to content

Instantly share code, notes, and snippets.

@MinhasKamal
Last active December 4, 2015 18:57
Show Gist options
  • Save MinhasKamal/9302016 to your computer and use it in GitHub Desktop.
Save MinhasKamal/9302016 to your computer and use it in GitHub Desktop.
This is a simple implementation of quick-sort algorithm in C language.
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
/**
* 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;
}
@MinhasKamal
Copy link
Author

Give it a file; the first line should be a value telling the number of integers, the rest will be input integers.

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