Быстрая сортировка Хоара - 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);
Объяснение кода листинга программы
- В функции sort(int*arr,int l,int r) происходит сортировка массива arr от индекса l до индекса r.
- Переменные i и j инициализируются значениями l и r соответственно.
- Переменная d инициализируется нулевым значением.
- Переменная m инициализируется значением arr[(l+r)/2]. Это средний элемент массива, который используется в качестве опорного элемента при сортировке.
- Цикл while(i<=j) повторяется до тех пор, пока i не станет больше j.
- Внутренний цикл for(; arr[i]<m; i++) перемещает i-й элемент, меньший чем опорный элемент, влево от i.
- Внутренний цикл for(; arr[j]>m; j--) перемещает j-й элемент, больший чем опорный элемент, вправо от j.
- Если внутренний цикл завершается, значит, элементы arr[i] и arr[j] уже находятся в правильном порядке. Их меняют местами и продолжают сортировку.
- Если элементы arr[i] и arr[j] находятся в неправильном порядке, их меняют местами, i увеличивают на 1, j уменьшают на 1 и продолжают сортировку.
- Если i становится больше j, это означает, что массив уже отсортирован, и функция может быть вызвана рекурсивно для сортировки других частей массива.
- Если j становится меньше i, это означает, что элементы arr[i] и arr[j] находятся в неправильном порядке, и функция должна быть вызвана рекурсивно для сортировки подмассива, начиная с индекса i и заканчивая индексом j.
- Переменная N инициализируется значением размера массива arr.
- Функция вызывается с параметрами arr, 0 и N-1, что означает сортировку всего массива arr.
- В результате выполнения функции массив arr будет отсортирован в порядке возрастания.
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д