Рубрики

Java программа для быстрой сортировки

Как и сортировка слиянием , QuickSort — это алгоритм «разделяй и властвуй». Он выбирает элемент как сводную и разделяет данный массив вокруг выбранной сводной. Существует много разных версий быстрой сортировки, которые выбирают сводную информацию по-разному.

  1. Всегда выбирайте первый элемент как опорный.
  2. Всегда выбирайте последний элемент как опорный (реализован ниже)
  3. Выберите случайный элемент как опорный.
  4. Выберите медиану как опору.

Ключевым процессом в быстрой сортировке является partition (). Цель разделов, заданная для массива и элемента x массива как pivot, поместить x в правильную позицию в отсортированном массиве и поместить все меньшие элементы (меньше x) перед x, а все большие элементы (больше x) после Икс. Все это должно быть сделано за линейное время.
Псевдокод для рекурсивной функции быстрой сортировки:

/* low  --> Starting index,  high  --> Ending index */
quickSort(arr[], low, high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[p] is now
           at right place */
        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

// Java-программа для реализации QuickSort

class QuickSort

{

    / * Эта функция принимает последний элемент в качестве оси,

       помещает элемент поворота в правильное положение

       положение в отсортированном массиве, и помещает все

       меньше (меньше, чем шарнир) слева от

       стержень и все большие элементы направо

       оси * /

    int partition(int arr[], int low, int high)

    {

        int pivot = arr[high]; 

        int i = (low-1); // индекс меньшего элемента

        for (int j=low; j<high; j++)

        {

            // Если текущий элемент меньше или

            // равно pivot

            if (arr[j] <= pivot)

            {

                i++;

  

                // поменять местами arr [i] и arr [j]

                int temp = arr[i];

                arr[i] = arr[j];

                arr[j] = temp;

            }

        }

  

        // поменять местами arr [i + 1] и arr [high] (или pivot)

        int temp = arr[i+1];

        arr[i+1] = arr[high];

        arr[high] = temp;

  

        return i+1;

    }

  

  

    / * Основная функция, которая реализует QuickSort ()

      arr [] -> Массив для сортировки,

      низкий -> Начальный индекс,

      высокий -> конечный индекс * /

    void sort(int arr[], int low, int high)

    {

        if (low < high)

        {

            / * pi - индекс разбиения, arr [pi] -

              сейчас в нужном месте * /

            int pi = partition(arr, low, high);

  

            // Рекурсивно сортировать элементы перед

            // раздел и после раздела

            sort(arr, low, pi-1);

            sort(arr, pi+1, high);

        }

    }

  

    / * Утилита для печати массива размером n * /

    static void printArray(int arr[])

    {

        int n = arr.length;

        for (int i=0; i<n; ++i)

            System.out.print(arr[i]+" ");

        System.out.println();

    }

  

    // Драйвер программы

    public static void main(String args[])

    {

        int arr[] = {10, 7, 8, 9, 1, 5};

        int n = arr.length;

  

        QuickSort ob = new QuickSort();

        ob.sort(arr, 0, n-1);

  

        System.out.println("sorted array");

        printArray(arr);

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

Пожалуйста, обратитесь к полной статье на QuickSort для более подробной информации!

Рекомендуемые посты:

Java программа для быстрой сортировки

0.00 (0%) 0 votes