Sort a List

Inspiration

There are many unsorted arrays and searching in unsorted arrays takes linear time complexity which can be optimised by sorting the array before searching. Searching in an sorted array takes logarithmic time complexity.

What it does

It sorts the array in increasing order.

How we built it

#include <iostream>
#include <vector>

using namespace std;

int partition(vector<int>& arr,int low,int high){
    int pivot = arr[low];
    int i = low;
    int j = high;

    while (i < j) {
        while (arr[i] <= pivot && i <= high - 1) {
            i++;
        }

        while (arr[j] > pivot && j >= low + 1) {
            j--;
        }
        if (i < j) swap(arr[i], arr[j]);
    }
    swap(arr[low], arr[j]);
    return j;
}

void quick_sort(vector<int>& arr,int low,int high){
    if(low < high){
        int pi = partition(arr,low,high);

        quick_sort(arr,low,pi-1);
        quick_sort(arr,pi+1,high);
    }
}

int main()
{
    vector<int> arr = {50,40,30,20,10};
    int n = 5;

    quick_sort(arr,0,n-1);

    for(auto it: arr){
        cout<<it<<" ";
    }

    return 0;
}

Challenges we ran into

Optimising the time complexity for sorting

Accomplishments that we're proud of

Achieving the optimised time complexity i.e. O(NlogN)

What we learned

Sorting an array

What's next for Sort a List

Built With

• c++