quick sort
static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } static int partition(int[] arr, int low, int high) { int pivot = arr[high]; // Index of smaller element and // indicates the right position // of pivot found so far int i = (low - 1); for(int j = low; j <= high - 1; j++) { // If current element is smaller // than the pivot if (arr[j] < pivot) { // Increment index of // smaller element i++; swap(arr, i, j); } } swap(arr, i + 1, high); return (i + 1); } static void quickSort(int[] arr, int low, int high) { if (low < high) { // pi is partitioning index, arr[p] // is now at right place int pi = partition(arr, low, high); // Separately sort elements before // partition and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } }
quick sort
def quicksort(arr): if len(arr) <= 1: return arr pivot = arr[len(arr) // 2] left = [x for x in arr if x < pivot] middle = [x for x in arr if x == pivot] right = [x for x in arr if x > pivot] return quicksort(left) + middle + quicksort(right) print(quicksort([3,6,8,10,1,2,1])) # Prints "[1, 1, 2, 3, 6, 8, 10]"
Source: cs231n.github.io
quick sort
def partition(start, end, array): # Initializing pivot's index to start pivot_index = start pivot = array[pivot_index] # This loop runs till start pointer crosses # end pointer, and when it does we swap the # pivot with element on end pointer while start < end: # Increment the start pointer till it finds an # element greater than pivot while start < len(array) and array[start] <= pivot: start += 1 # Decrement the end pointer till it finds an # element less than pivot while array[end] > pivot: end -= 1 # If start and end have not crossed each other, # swap the numbers on start and end if(start < end): array[start], array[end] = array[end], array[start] # Swap pivot element with element on end pointer. # This puts pivot on its correct sorted place. array[end], array[pivot_index] = array[pivot_index], array[end] # Returning end pointer to divide the array into 2 return end # The main function that implements QuickSort def quick_sort(start, end, array): if (start < end): # p is partitioning index, array[p] # is at right place p = partition(start, end, array) # Sort elements before partition # and after partition quick_sort(start, p - 1, array) quick_sort(p + 1, end, array)
quick_sort
void quick_sort(int q[], int l, int r) { if (l >= r) return; int i = l - 1, j = r + 1, x = q[l + r >> 1]; while (i < j) { do i ++ ; while (q[i] < x); do j -- ; while (q[j] > x); if (i < j) swap(q[i], q[j]); } quick_sort(q, l, j), quick_sort(q, j + 1, r); }
Source: www.acwing.com
Quick_sort
//piv: Pivot element int partition ( int A[],int start ,int end) { int i = start + 1; int piv = A[start] ; //make the first element as pivot element. for(int j =start + 1; j <= end ; j++ ) { /*rearrange the array by putting elements which are less than pivot on one side and which are greater that on other. */ if ( A[ j ] < piv) { swap (A[ i ],A [ j ]); i += 1; } } swap ( A[ start ] ,A[ i-1 ] ) ; //put the pivot element in its proper place. return i-1; //return the position of the pivot } // recursive function Quick_sort: void quick_sort ( int A[ ] ,int start , int end ) { if( start < end ) { //stores the position of pivot element int piv_pos = partition (A,start , end ) ; quick_sort (A,start , piv_pos -1); //sorts the left side of pivot. quick_sort ( A,piv_pos +1 , end) ; //sorts the right side of pivot. } }
Quick sort
// Take Left (first) Index of the array and Right (last) Index of the array void quickSort(int Data[], int l , int r) { // If the first index less or equal than the last index if (l <= r) { // Create a Key/Pivot Element int key = Data[(l+r)/2]; // Create temp Variables to loop through array int i = l; int j = r; while (i <= j) { while (Data[i] < key) i++; while (Data[j] > key) j--; if (i <= j) { swap(Data[i], Data[j]); i++; j--; } } // Recursion to the smaller partition in the array after sorted above if (l < j) quickSort(Data, l, j); if (r > i) quickSort(Data, i, r); } }
Source: www.stdio.vn
quick sort
function swap(arr, leftIndex, rightIndex){ // swap 2 elements in the array var temp = arr[leftIndex]; arr[leftIndex] = arr[rightIndex]; arr[rightIndex] = temp; } function partition(arr, left, right) { var pivot = arr[Math.floor((right + left) / 2)], //middle element i = left, //left pointer j = right; //right pointer while (i <= j) { // while left pointer is smaller than right pointer while (arr[i] < pivot) { // move the left pointer to the right i++; } while (arr[j] > pivot) { // move the right pointer to the left j--; } if (i <= j) { //left pointer smaller or equal to right pointer swap(arr, i, j); //sawpping two elements i++; j--; } } return i; } // run as quickSort(array, 0, array.length - 1); function quickSort(arr, left, right) { var index; if (arr.length > 1) { index = partition(arr, left, right); //index returned from partition if (left < index - 1) { //more elements on the left side of the pivot quickSort(arr, left, index - 1); } if (index < right) { //more elements on the right side of the pivot quickSort(arr, index, right); } } return arr; }
Source: sorting-algorithms.me