Sorts
Quick Sort
Quick sortQuicksort is a divide and conquer algorithm. It first divides the input array into two smaller sub-arrays: the low elements and the high elements. It then recursively sorts the sub-arrays.
Example :
Quick sortQuicksort is a divide and conquer algorithm. It first divides the input array into two smaller sub-arrays: the low elements and the high elements. It then recursively sorts the sub-arrays.
Example :
Algorithm Quicksort [A (0..n-1)]
// Sort a given array by Quick sort.
// Input : An array A(0,n-1) of orderable elements.
// Output : Array A [0,n-1] sorted in non- decreasing order .
if low < high then
p := partition(A, low, high)
quicksort(A, low, p - 1)
quicksort(A, p + 1, high)
Algorithm partition(A, low, high)
pivot := A[high]
i := lo
for j := low to high do
if A[j] < pivot then
swap A[i] with A[j]
i := i + 1
swap A[i] with A[hi]
return i
#include< stdio.h>
void quicksort(int number[25],int first,int last){
int i, j, pivot, temp;
if(first< last){
pivot=first;
i=first;
j=last;
while(i< j){
while(number[i]<=number[pivot]&&i< last)
i++;
while(number[j] >number[pivot])
j--;
if(i< j){
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
quicksort(number,first,j-1);
quicksort(number,j+1,last);
}
}
int main(){
int i, count, number[25];
printf("How many elements are u going to enter?: ");
scanf("%d",&count);
printf("Enter %d elements: ", count);
for(i=0;i< count;i++)
scanf("%d",&number[i]);
quicksort(number,0,count-1);
printf("Order of Sorted elements: ");
for(i=0;i< count;i++)
printf(" %d",number[i]);
return 0;
}
Code
import java.util.*;
class QuickSort {
//selects last element as pivot, pi using which array is partitioned.
int partition(int intArray[], int low, int high) {
int pi = intArray[high];
int i = (low-1); // smaller element index
for (int j=low; j< high; j++) {
// check if current element is less than or equal to pi
if (intArray[j] <= pi) {
i++;
// swap intArray[i] and intArray[j]
int temp = intArray[i];
intArray[i] = intArray[j];
intArray[j] = temp;
}
}
// swap intArray[i+1] and intArray[high] (or pi)
int temp = intArray[i+1];
intArray[i+1] = intArray[high];
intArray[high] = temp;
return i+1;
}
//routine to sort the array partitions recursively
void quick_sort(int intArray[], int low, int high) {
if (low < high) {
//partition the array around pi=>partitioning index and return pi
int pi = partition(intArray, low, high);
// sort each partition recursively
quick_sort(intArray, low, pi-1);
quick_sort(intArray, pi+1, high);
}
}
}
class Main{
public static void main(String args[]) {
//initialize a numeric array, intArray
int intArray[] = {4,-1,6,8,0,5,-3};
int n = intArray.length;
//print the original array
System.out.println("Original Array: " + Arrays.toString(intArray));
//call quick_sort routine using QuickSort object
QuickSort obj = new QuickSort();
obj.quick_sort(intArray, 0, n-1);
//print the sorted array
System.out.println("\nSorted Array: " + Arrays.toString(intArray));
}
}
Code
# divide function
def partition(arr,low,high):
i = ( low-1 )
pivot = arr[high] # pivot element
for j in range(low , high):
# If current element is smaller
if arr[j] <= pivot:
# increment
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )
# sort
def quickSort(arr,low,high):
if low < high:
# index
pi = partition(arr,low,high)
# sort the partitions
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
# main
arr = [2,5,3,8,6,5,4,7]
n = len(arr)
quickSort(arr,0,n-1)
print ("Sorted array is:")
for i in range(n):
print (arr[i],end=" ")
Code
5 3 2 5 8 7 6
2 3 4 5 5 6 7 8
best case, average case, worst case
Shell sort
Breadth-first-search