Короткий рекурсивный QuickSort для целочисленного массива и массива строк

Собственно, сабж, чтоб не завалялось. Проверено в Visual C++ 2010 Express, сработало. Примерно как описано в русской Вики, только там нет C++-реализации.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
using namespace std;

void quickSort(int arr[], int left, int right) {
 int i = left, j = right;
 int tmp;
 int middle = arr[(left + right) / 2];
 while (i <= j) {
  while (arr[i] < middle) i++;
  while (arr[j] > middle) j--;
  if (i <= j) {
   //или делать здесь обмен 2 записей,
   //если с массивом сортируем что-то ещё
   tmp = arr[i];
   arr[i] = arr[j];
   arr[j] = tmp;
   i++;
   j--;
  }
 };
 if (left < j)
  quickSort(arr, left, j);
 if (i < right)
  quickSort(arr, i, right);
}

int main() {
 const int n = 10;
 int a[] = {1, 12, 5, 26, 7, 14, 3, 7, 2, 12};
 quickSort(a, 0, n-1);
 for (int i=0; i<n; i++) cout << a[i] << " ";
 cin.get(); cin.sync(); return 0;
}

Вот версия для массива Си-строк:

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
using namespace std;

const int maxlen = 15; //максимальная длина строки уже известна
const int N=10; //количество строк тоже известно

void _qsort1 (char *arr[],int left,int right) {
 int i = left, j = right;
 char *tmp = new char[maxlen+1];
 char *middle = new char[maxlen+1];
 strcpy( middle , arr[(left + right) / 2]);
 while (i <= j) {
  while (strcmp(arr[i],middle)<0) i++;
  while (strcmp(arr[j],middle)>0) j--;
  if (i <= j) {
   strcpy (tmp , arr[i]);
   strcpy (arr[i] , arr[j]);
   strcpy (arr[j] , tmp);
   i++;
   j--;
  }
 };
 if (left < j)
  _qsort1(arr, left, j);
 if (i < right)
  _qsort1(arr, i, right);
}

void _qsort (int n,char **buf) {
 _qsort1 (buf,0,n-1);
}

int main() {
 char **buf; //буфер для сортировки
 buf = new char * [N];
 for (int i=0; i<N; i++) buf[i] = new char [maxlen+1]; 
 strcpy (buf[0],"zdanov");
 strcpy (buf[1],"chichalov");
 strcpy (buf[2],"degtyarev");
 strcpy (buf[3],"ermolaev");
 strcpy (buf[4],"sidorov");
 strcpy (buf[5],"sidorenko");
 strcpy (buf[6],"straustroop");
 strcpy (buf[7],"podbelskiy");
 strcpy (buf[8],"tarakanova");
 strcpy (buf[9],"kant");

 _qsort1 (buf,0,N-1);
 for (int i=0; i<N; i++) cout << buf[i] << endl;
 cin.sync(); cin.get(); return 0;
}

27.11.2015, 15:08 [5822 просмотра]