Algorithms Code Quick Sort

@ Mr. Eric | Sunday, May 29, 2022 | 6 minute read | Update at Sunday, May 29, 2022

How does quick sort work, in the first place?

Well, quick sort is another sorting method, and according to its name, it’s quick. In fact, it is actually one of the most popular sorting methods amongst them all! But why is it so popular? Because it is quick, and also, it can sort huge amounts of data, such as this one, 100 million numbers is no problem! But back to the topic, how does quick work?

The way it works is like this. Suppose you have an array, {9,6,3,10,2,1} (But I figured out that it’s a little bit special. Anyways, since it can work in any data set, let’s keep going.) After the first step it’ll look like this: {2,6,3,1,9,10}. But how? That’s the complicated step. But first, can you notice a pattern in the array after the first step? Look for a few seconds. You might’ve noticed that on the left side of {9}, the other elements are all smaller, and on the right side, the elements are bigger. But how? How did we do this? This is only one way of quick sorting by the way. Let’s get right into the first step!

Step 1’s train of thought: So what we want to do now is to sort the elements so that on the left of an element, the numbers are smaller, and on the right they’re bigger.

Step.1’: Now, let’s select the element which is going to be in the middle (I don’t know a more accurate word sorry). We’ll call this element the pivot. There are different way’s of choosing the pivot, e.g (I finally learnt the difference between e.g and i.e!) using the first element as the pivot, using the last element, even using the middle element! But today I’ll only talk about the first one. We also have the variable {i}, which is set to total of elements in array {+1}. You’ll see why later :)

Step 1.2: Now that we have our pivot, we’ll have to search from the top (The last element) to the bottom (The second-to-first element) for a special number. This number is very special, because it’s the first number which is smaller than the pivot that we bump into while searching. Then, we subtract {i} by one, and swap this very special number with the {i}th element in the array. If you got this step, then all we have to do next is to repeat this process (Note that every search after the first starts not from the top, but from the next element from the VIP number we found before) care-freely until the search reaches the bottom. For this array, it should look like {9,6,3,1,2,10} when the search ends.

Step 1.3: We reached the bottom! Hooray! But no time for celebrations. We got to keep moving! After that, we’ll swap the pivot with the {i}th element (if you kept count of {i}, which you probably should) in the array. Once we’re done, our array should look like this: {2,6,3,1,9,10}. We reached our goal! Make sure to keep up and catch your breath and move on! After you placed the pivot in the middle, you need to split the array like this: {2,6,1,3,9} and {10}. But, you might ask, where on earth is the pivot? This is time to say goodbye to him, because after you split the array, the two arrays shouldn’t have the pivot in any of them! And all we need to do now, is to use the same step over and over again to these two arrays (Or maybe even more after the first one split up!)

That’s it for the introduction of quick sort. If you want to see the animation, go to this cool animation page, and for better understanding, well, I recommend you read it through again, or go to very trusty page of explanation!

Oh man, 100 million elements must be a lot! How did you manage that? (Computer: Thanks a lot guys. I need a break)

To be honest, actually just follow this train of thought, and you can come up with your own code! But also, I recommend you not to print it, or else you’ll spend years reading it through, and you’ll probably be an old man after that. I recommend you get Sublime Text or other apps to show files (I really recommend Sublime Text because it’s so trusty that it actually showed 100 million data without any lagging! Just make sure your computer is ready for a super-hard challenge), and then store the unsorted data in one file and the sorted one in another! And also, I came up with my own code, but the code I’m using is a changed version of c-language code in this website. Why? Because this person is absolutely a genius! You might want to come up with your own code and compare it - and you might find out that he’s a genius.

Here’s my code! However, again this is only my personal way of quick sorting!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define TOTAL 100000000
#define UPPER 1000000000
#define LOWER 0

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int array[], int low, int high)
{
    int pivot = array[low];
    int i = high + 1;
    for(int j = high; j > low; j--)
    {
        if(array[j] >= pivot)
        {
            i--;
            swap(&array[i], &array[j]);
        }
    }
    swap(&array[i - 1], &array[low]);
    return (i - 1);
}

void quickSort(int array[], int low, int high)
{
    if(low < high)
    {
        int pi = partition(array, low, high);
        quickSort(array, low, pi - 1);
        quickSort(array, pi + 1, high);
    }
}

int main(void)
{
    clock_t startc = clock();
    static int lista[TOTAL];
    srand(time(NULL));
    for(int i = 0; i < TOTAL; i++)
    {
        lista[i] = (rand() % (UPPER - LOWER + 1)) + LOWER;
    }
    FILE *F1, *F2;
    F1 = fopen("data_set1.txt", "w");
    if(F1 == NULL)
    {
        printf("Error: File opened unsuccessfully\n");
    }
    else
    {
        printf("data_set1.txt opend successfully\n");
        for(int j = 0; j < TOTAL; j++)
        {
            fprintf(F1, "%d\n", lista[j]);
        }
        printf("Data set generated successfully\n");
        fclose(F1);
    }
    clock_t starts = clock();
    quickSort(lista, 0, TOTAL - 1);
    clock_t ends = clock();
    double stime = (double)(ends - starts) / CLOCKS_PER_SEC;
    F2 = fopen("data_set2.txt", "w");
    if(F2 == NULL)
    {
        printf("Error: File opened unseccessfully\n");
    }
    else
    {
        printf("data_set2.txt opened successfully\n");
        for(int k = 0; k < TOTAL; k++)
        {
            fprintf(F2, "%d\n", lista[k]);
        }
        printf("Data set sorted successfully\n");
        fclose(F2);
    }
    clock_t endc = clock();
    double wtime = (double)(endc - startc)  / CLOCKS_PER_SEC;
    printf("You used %f amount of time with sorting, and %f amount time with the whole code\n", stime, wtime);
    return 0;
}