Быстрая сортировка Хоара - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Здрасьте. Вот писал быструю сортировку Хоара на Си, вроде все сделал, а на практике она часто не полностью сортирует массив, особенно с большой длиной. Никак не могу понять, почему. То есть она его сортирует, но некоторые числа стоят не на своем месте.
void hSort(int *A, int N) //N - длина массива A
{
    int tmp;
    if (N <= 1)
        return;
    int l = 0, r = N - 1; //l - левая граница, r - правая
    int pivot = A[rand()%N];
    while (l != r)
    {
        if (A[l] >= pivot)
        {
            if (A[r] < pivot)
            {
                tmp = A[l];
                A[l] = A[r];
                A[r] = tmp;
                l++;
            }
            if (l != r) r--;
        }
        else l++;
    }
    if (A[0] == A[N-1]) return; //проверка на то, что мы сортируем не одинаковые элементы, чтоб не зацикл.
    hSort(A, l);
    hSort(A + l, N-l);
}

Решение задачи: «Быстрая сортировка Хоара»

textual
Листинг программы
void sort(int*arr,int l,int r)
{
    int i=l, j=r;
    int d;
    int m=arr[(l+r)/2];
    while(i<=j)
    {
        for(; arr[i]<m; i++);
        for(; arr[j]>m; j--);
        if(i<=j)
        {
            d=arr[i];
            arr[i++]=arr[j];
            arr[j--]=d;
        }
    }
    if(l<j) sort(arr,l,j);
    if(i<r) sort(arr,i,r);
 
}
..................
sort(arr,0,N-1);

Объяснение кода листинга программы

  1. В функции sort(int*arr,int l,int r) происходит сортировка массива arr от индекса l до индекса r.
  2. Переменные i и j инициализируются значениями l и r соответственно.
  3. Переменная d инициализируется нулевым значением.
  4. Переменная m инициализируется значением arr[(l+r)/2]. Это средний элемент массива, который используется в качестве опорного элемента при сортировке.
  5. Цикл while(i<=j) повторяется до тех пор, пока i не станет больше j.
  6. Внутренний цикл for(; arr[i]<m; i++) перемещает i-й элемент, меньший чем опорный элемент, влево от i.
  7. Внутренний цикл for(; arr[j]>m; j--) перемещает j-й элемент, больший чем опорный элемент, вправо от j.
  8. Если внутренний цикл завершается, значит, элементы arr[i] и arr[j] уже находятся в правильном порядке. Их меняют местами и продолжают сортировку.
  9. Если элементы arr[i] и arr[j] находятся в неправильном порядке, их меняют местами, i увеличивают на 1, j уменьшают на 1 и продолжают сортировку.
  10. Если i становится больше j, это означает, что массив уже отсортирован, и функция может быть вызвана рекурсивно для сортировки других частей массива.
  11. Если j становится меньше i, это означает, что элементы arr[i] и arr[j] находятся в неправильном порядке, и функция должна быть вызвана рекурсивно для сортировки подмассива, начиная с индекса i и заканчивая индексом j.
  12. Переменная N инициализируется значением размера массива arr.
  13. Функция вызывается с параметрами arr, 0 и N-1, что означает сортировку всего массива arr.
  14. В результате выполнения функции массив arr будет отсортирован в порядке возрастания.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

14   голосов , оценка 4 из 5