Компьютеры
и программирование

АЛГОРИТМЫ СОРТИРОВКИ: РЕАЛИЗАЦИЯ НА С++

Сортировка выбором (Selection sort)

Пузырьковая сортировка (Bubble sort)

Сортировка вставками (Insertion sort)

Сортировка слиянием (Merge sort)

Быстрая сортировка (Quick sort)

Было подсчитано, что до четверти времени централизованных компьютеров уделяется сортировке данных. Это потому, что намного легче найти значение в массиве, который был заранее отсортирован. В противном случае поиск немного походит на поиск иголки в стоге сена.

Есть программисты, которые всё рабочее время проводят в изучении и внедрении алгоритмов сортировки. Это потому, что подавляющее большинство программ в бизнесе включает в себя управление базами данных. Люди ищут информацию в базах данных всё время. Это означает, что поисковые алгоритмы очень востребованы.

Но есть одно "но". Поисковые алгоритмы работают намного быстрее с базами данных, которые уже отсортированы. В этом случае требуется только линейный поиск.

В то время как компьютеры находятся без пользователей в некоторые моменты времени, алгоритмы сортировки продолжают работать с базами данных. Снова приходят пользователи, осуществляющие поиск, а база данных уже отсортирована, исходя из той или иной цели поиска.

В этой статье приведены примеры реализации стандартных алгоритмов сортировки.

Сортировка выбором (Selection sort)

Для того, чтобы отсортировать массив в порядке возрастания, следует на каждой итерации найти элемент с наибольшим значением. С ним нужно поменять местами последний элемент. Следующий элемент с наибольшим значением становится уже на предпоследнее место. Так должно происходить, пока элементы, находящиеся на первых местах в массивe, не окажутся в надлежащем порядке.

Код C++

void SortAlgo::selectionSort(int data[], int lenD) { int j = 0; int tmp = 0; for(int i=0; i<lenD; i++){ j = i; for(int k = i; k<lenD; k++){ if(data[j]>data[k]){ j = k; } } tmp = data[i]; data[i] = data[j]; data[j] = tmp; } }

Пузырьковая сортировка (Bubble sort)

При пузырьковой сортировке сравниваются соседние элементы и меняются местами, если следующий элемент меньше предыдущего. Требуется несколько проходов по данным. Во время первого прохода сраваются первые два элемента в массиве. Если они не в порядке, они меняются местами и затем сравнивается элементы в следующей паре. При том же условии они так же меняются местами. Таким образом сортировка происходит в каждом цикле пока не будет достигнут конец массива.

Код C++

void SortAlgo::bubbleSort(int data[], int lenD) { int tmp = 0; for(int i = 0;i<lenD;i++){ for(int j = (lenD-1);j>=(i+1);j--){ if(data[j]<data[j-1]){ tmp = data[j]; data[j]=data[j-1]; data[j-1]=tmp; } } } }

Сортировка вставками (Insertion sort)

При сортировке вставками массив разбивается на две области: упорядоченную и и неупорядоченную. Изначально весь массив является неупорядоченной областью. При первом проходе первый элемент из неупорядоченной области изымается и помещается в правильном положении в упорядоченной области.

На каждом проходе размер упорядоченной области возрастает на 1, а размер неупорядоченной области сокращается на 1.

Основной цикл работает в интервале от 1 до N-1. На j-й итерации элемент [i] вставлен в правильное положение в упорядоченной области. Это сделано путем сдвига всех элементов упорядоченной области, которые больше, чем [i], на одну позицию вправо. [i] вставляется в интервал между теми элементами, которые меньше [i], и теми, которые больше [i].

Код C++

void SortAlgo::insertionSort(int data[], int lenD) { int key = 0; int i = 0; for(int j = 1;j<lenD;j++){ key = data[j]; i = j-1; while(i>=0 && data[i]>key){ data[i+1] = data[i]; i = i-1; data[i+1]=key; } } }

Сортировка слиянием (Merge sort)

При рекурсивной сортировке слиянием массив сначала разбивается на мелкие кусочки - на первом этапе - на состоящие из одного элемента. Затем эти кусочки объединяются в более крупные кусочки - по два элемента и элементы при этом сравниваются, а в результате в новом кусочке меньший элемент занимает место слева, а больший - справа. Далее происходит слияние в ещё более крупные кусочки и так до конца алгоритма, когда все кусочки будут объединены в один, уже отсортированный массив. Если есть интерес, есть статья о рекурсивных функциях.

Код C++

void SortAlgo::mergeSort(int data[], int lenD) { if(lenD>1){ int middle = lenD/2; int rem = lenD-middle; int* L = new int[middle]; int* R = new int[rem]; for(int i=0;i<lenD;i++){ if(i<middle){ L[i] = data[i]; } else{ R[i-middle] = data[i]; } } mergeSort(L,middle); mergeSort(R,rem); merge(data, lenD, L, middle, R, rem); } } void SortAlgo::merge(int merged[], int lenD, int L[], int lenL, int R[], int lenR){ int i = 0; int j = 0; while(i<lenL||j<lenR){ if (i<lenL & j<lenR){ if(L[i]<=R[j]){ merged[i+j] = L[i]; i++; } else{ merged[i+j] = R[j]; j++; } } else if(i<lenL){ merged[i+j] = L[i]; i++; } else if(j<lenR){ merged[i+j] = R[j]; j++; } } }

Быстрая сортировка (Quick sort)

Быстрая сортировка использует алгоритм "разделяй и властвуй". Она начинается с разбиения исходного массива на две области. Эти части находятся слева и справа от отмеченного элемента, называемого опорным. В конце процесса одна часть будет содержать элементы меньшие, чем опорный, а другая часть будет содержать элементы больше опорного.

Код C++

void SortAlgo::quickSort(int* data, int const len) { int const lenD = len; int pivot = 0; int ind = lenD/2; int i,j = 0,k = 0; if(lenD>1){ int* L = new int[lenD]; int* R = new int[lenD]; pivot = data[ind]; for(i=0;i<lenD;i++){ if(i!=ind){ if(data[i]<pivot){ L[j] = data[i]; j++; } else{ R[k] = data[i]; k++; } } } quickSort(L,j); quickSort(R,k); for(int cnt=0;cnt<lenD;cnt++){ if(cnt<j){ data[cnt] = L[cnt];; } else if(cnt==j){ data[cnt] = pivot; } else{ data[cnt] = R[cnt-(j+1)]; } } } }

Весь блок Программирование C++

К началу страницы

Поделиться с друзьями