hacktoberfest

Your first pull request

It picks an element as a pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

Always pick the first element as a pivot. Always pick the last element as a pivot (implemented below) Pick a random element as a pivot. Pick median as the pivot. The key process in quickSort is a partition(). The target of partitions is, given an array and an element x of an array as the pivot, put x at its correct position in a sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

Pseudo Code for recursive QuickSort function:

/* low –> Starting index, high –> Ending index */

quickSort(arr[], low, high) {

if (low < high) {

    /* pi is partitioning index, arr[pi] is now at right place */

    pi = partition(arr, low, high);

    quickSort(arr, low, pi – 1);  // Before pi

    quickSort(arr, pi + 1, high); // After pi

}

}

Pseudo code for partition()

/* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */

partition (arr[], low, high) { // pivot (Element to be placed at right position) pivot = arr[high];

i = (low – 1)  // Index of smaller element and indicates the 
// right position of pivot found so far

for (j = low; j <= high- 1; j++){

    // If current element is smaller than the pivot
    if (arr[j] < pivot){
        i++;    // increment index of smaller element
        swap arr[i] and arr[j]
    }
}
swap arr[i + 1] and arr[high])
return (i + 1)

}

// here i use lomoto algo for partation you can go with Hoar's also

Bubble sort

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order (ascending or descending arrangement). The pass through the list is repeated until no swaps are needed which indicates that the list is sorted.

Complexity

Name	Best	Average	Worst	Memory	Stable	Comments
Bubble sort	n	n2	n2	1	Yes

Algorithm

static void bubbleSort(int arr[], int n)
    {
        int i, j, temp;
        boolean swapped;
        for (i = 0; i < n - 1; i++)
        {
            swapped = false;
            for (j = 0; j < n - i - 1; j++)
            {
                if (arr[j] > arr[j + 1])
                {
                    // swap arr[j] and arr[j+1]
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
 
            // IF no two elements were
            // swapped by inner loop, then break
            if (swapped == false)
                break;
        }
    }

Merge Sort

Merge Sort is one of the most popular sorting algorithms that is based on the principle of Divide and Conquer Algorithm. A problem is divided into multiple sub-problems. Each sub-problem is solved individually. Finally, sub-problems are combined to form the final solution.

Example

Complexity

Name	Best	Average	Worst	Memory	Stable	Comments
Merge sort	nlogn	nlogn	nlogn	n	Yes

Algorithm

Merge_Sort(arr, beg, end)  
 
if beg < end  then
mid = (beg + end)/2  
Merge_Sort(arr, beg, mid)  
Merge_Sort(arr, mid + 1, end)  
Merge (arr, beg, mid, end)  
end of if  
 
End Merge_Sort

Code for Merge function

void merge(int arr[],int low,int mid,int high)
   {
        
       int i,j,k,t[]=new int[max];
       i=low;
       k=low;
       j=mid+1;
       while(i<=mid && j<=high)
       {
         if(arr[i]<a[j])
         t[k++]=a[i++];
         else
          t[k++]=arr[j++];
          
       }
       while(i<=mid)
        t[k++]=arr[i++];
        while(j<=high)
        t[k++]=arr[j++];
        for(i=low;i<=high;i++)
        arr[i]=t[i];
   }