Компьютеры
и программирование
Форум
Тесты онлайн

Алгоритмы сортировки: реализация на С++

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

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

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

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

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

Сортировка выбором (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++
К началу страницы

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