Алгоритам КуицкСорт

У овом упутству ћете научити како функционише брзи сортирање. Такође, наћи ћете радне примере брзог сортирања у Ц, Ц ++ Питхон и Јава.

Куицксорт је алгоритам заснован на приступу подијели и владај у којем је низ подијељен на поднизове и ти поднизови се рекурзивно позивају за сортирање елемената.

Како КуицкСорт ради?

  1. Из низа се бира пивот елемент. Као пивот елемент можете одабрати било који елемент из низа.
    Овде смо узели крајњи десни (тј. Последњи елемент) низа као пивот елемент. Изаберите пивот елемент
  2. Елементи мањи од пивот елемента стављају се лево, а елементи већи од пивот елемента десно. Све мање елементе ставите лево, а веће десно десни део окретног елемента
    . Горњи распоред постиже се следећим корацима.
    1. Показивач је фиксиран на осовинском елементу. Пивот елемент се упоређује са елементима који почињу од првог индекса. Ако се достигне елемент већи од елемента закретања, поставља се други показивач за тај елемент.
    2. Сада се пивот елемент упоређује са осталим елементима (трећи показивач). Ако се дође до елемента мањег од пивот елемента, мањи елемент се замењује већим елементом који је пронађен раније. Поређење стожног елемента са осталим елементима
    3. Процес траје док се не постигне други последњи елемент.
      На крају, пивот елемент се замењује другим показивачем. Замените пивот елемент са другим показивачем
    4. Сада су леви и десни поддео овог стожног елемента узети за даљу обраду у доњим корацима.
  3. Елементи закретања се поново бирају за леви и десни поддео одвојено. Унутар ових подделова, осовински елементи постављени су у прави положај. Затим се понавља корак 2. Изаберите пивот елемент из сваке половине и поставите на тачно место помоћу рекурзије
  4. Подделови су поново подељени на мање подделове све док сваки поддео није формиран од једног елемента.
  5. У овом тренутку, низ је већ сортиран.

Куицксорт користи рекурзију за сортирање подделова.

На основу приступа подели и освоји, алгоритам брзог сортирања може се објаснити као:

  • Подијели
    Низ је подијељен на дијелове који узимају пивот као тачку партиционирања. Елементи мањи од осовине постављени су лево од осовине, а елементи већи од осовине постављени су десно.
  • Цонкуер
    Леви и десни Поглавља су поново подељена користећи избором заокретне елементи за њих. То се може постићи рекурзивним прослеђивањем подделова у алгоритам.
  • Комбиновање
    Овај корак не игра значајну улогу у брзом сортирању. Низ је већ сортиран на крају корака освајања.

Можете да разумете рад брзог сортирања помоћу илустрација у наставку.

Сортирање елемената лево од пивота помоћу рекурзије Сортирање елемената десно од пивота помоћу рекурзије

Алгоритам брзог сортирања

 куицкСорт (арраи, лефтмостИндек, ригхтмостИндек) иф (лефтмостИндек <ригхтмостИндек) пивотИндек <- партиција (арраи, лефтмостИндек, ригхтмостИндек) куицкСорт (арраи, лефтмостИндек, пивотИндек) куицкСорт (арраи, пивотИндек, леви крајњи индекс, десни крајњи индекс, десни крајњи индекс, десни крајњи индекс, најкраћи индекс десно ) поставите ригхтмостИндек као пивотИндек стореИндек <- лефтмостИндек - 1 за и <- лефтмостИндек + 1 на ригхтмостИндек иф елемент (и) <пивотЕлемент свап елемент (и) и елемент (стореИндек) стореИндек ++ свап пивотЕлемент и елемент (стореИндек + 1) ретурн стореИндек + 1

Примери за Питхон, Јава и Ц / Ц ++

Питхон Јава Ц Ц + 
 # Quick sort in Python # Function to partition the array on the basis of pivot element def partition(array, low, high): # Select the pivot element pivot = array(high) i = low - 1 # Put the elements smaller than pivot on the left and greater #than pivot on the right of pivot for j in range(low, high): if array(j) <= pivot: i = i + 1 (array(i), array(j)) = (array(j), array(i)) (array(i + 1), array(high)) = (array(high), array(i + 1)) return i + 1 def quickSort(array, low, high): if low < high: # Select pivot position and put all the elements smaller # than pivot on left and greater than pivot on right pi = partition(array, low, high) # Sort the elements on the left of pivot quickSort(array, low, pi - 1) # Sort the elements on the right of pivot quickSort(array, pi + 1, high) data = (8, 7, 2, 1, 0, 9, 6) size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data)
 // Quick sort in Java import java.util.Arrays; class QuickSort ( // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left and // greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; int temp = array(i); array(i) = array(j); array(j) = temp; ) ) int temp = array(i + 1); array(i + 1) = array(high); array(high) = temp; return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code public static void main(String args()) ( int() data = ( 8, 7, 2, 1, 0, 9, 6 ); int size = data.length; QuickSort qs = new QuickSort(); qs.quickSort(data, 0, size - 1); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
 // Quick sort in C #include // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Function to print eklements of an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (8, 7, 2, 1, 0, 9, 6); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); printf("Sorted array in ascending order: "); printArray(data, n); )
 // Quick sort in C++ #include using namespace std; // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to print eklements of an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) printArray(array, 7); cout << "… "; swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code int main() ( int data() = (8, 7, 6, 1, 0, 9, 2); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); cout << "Sorted array in ascending order: "; printArray(data, n); )

Куицксорт Цомплекити

Сложеност времена

  • Најгори случај сложености (Биг-О) : Појављује се када је изабрани пивот елемент или највећи или најмањи елемент. Овај услов доводи до случаја када се пивот елемент налази на крајњем крају сортираног низа. Један под-низ је увек празан, а други под-низ садржи елементе. Дакле, брзи сортирање се позива само на овом под-низу. Међутим, алгоритам брзог сортирања има боље перформансе за раштркане пивоте.O(n2)
    n - 1

  • Сложеност најбољег случаја (Биг-омега) : O(n*log n)
    Појављује се када је стожерни елемент увек средњи елемент или близу средњег елемента.
  • Просечна сложеност случаја (Биг-тхета) : O(n*log n)
    Јавља се када се не појаве горе наведени услови.

Сложеност простора

Сложеност простора за брзи сорти је O(log n).

Куицксорт Апплицатионс

Куицксорт се примењује када

  • програмски језик је добар за рекурзију
  • сложеност времена је битна
  • сложеност простора је битна

Занимљиви Чланци...