|
QuickSort dasturini amalga oshirish uchun
|
| bet | 10/16 | | Sana | 15.11.2023 | | Hajmi | 29,81 Mb. | | #99092 |
Bog'liq Dilshoda Algoritm mustaqil QuickSort dasturini amalga oshirish uchun:
Algoritmni amalga oshirish uchun quyidagi bosqichlarni bajaring:
Tez tartiblashni amalga oshirish uchun rekursiv funksiya yarating (aytaylik, quicksort() ).
Saralanadigan diapazonni bo'ling (dastlab diapazon 0 dan N-1 gacha ) va pivotning to'g'ri o'rnini qaytaring (aytaylik, pi ).
Pivot bo'lish uchun diapazonning eng o'ngdagi qiymatini tanlang.
Chapdan takrorlang va elementni pivot bilan solishtiring va yuqorida ko'rsatilgandek bo'limni bajaring.
Burilishning to'g'ri holatini qaytaring.
Pi ning chap va o'ng qismi uchun tezkor saralashni takroran chaqiring .
Quyida Quicksort dasturining amalga oshirilishi keltirilgan:
// C# implementation of QuickSort
using System;
class GFG {
// A utility function to swap two elements
static void swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// This function takes last element as pivot,
// places the pivot element at its correct position
// in sorted array, and places all smaller to left
// of pivot and all greater elements to right of pivot
static int partition(int[] arr, int low, int high)
{
// Choosing the pivot
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);
}
// The main function that implements QuickSort
// arr[] --> Array to be sorted,
// low --> Starting index,
// high --> Ending index
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
// and after partition index
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Driver Code
public static void Main()
{
int[] arr = { 10, 7, 8, 9, 1, 5 };
int N = arr.Length;
// Function call
quickSort(arr, 0, N - 1);
Console.WriteLine("Sorted array:");
for (int i = 0; i < N; i++)
Console.Write(arr[i] + " ");
}
}
Chiqish
Saralangan massiv: 1 5 7 8 9 10
|
| |
