Алгоритмы сортировки массива (CPP)


Сортировка массивов - классическая тема теории алгоритмов.
Самые известные методы сортировки массива чисел приведены ниже.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <string.h>

const int N = 33;

void swap(int &x, int &y)
{
    int z=x; x=y; y=z;
}

int randRange(int lower,int upper)
{
    return rand() % (upper-lower+1) + lower;
}

void showArray(int *a)
{
    for(int i=0;i<N;i++)
    {
        printf("%2d ",*(a+i));
    }
    printf("\n");
}

// Алгоритм вставки - slowest
void sortInsertion(int *a)
{
    for(int i=1;i<N;i++)
    {
        int tmp = a[i];
        int j=i;
        for(j=i;j>0;j--)
        {
            if (a[j-1]>tmp) a[j]=a[j-1]; else break;
        }
        a[j]=tmp;
    }
}

// Алгоритм пузырька
void sortBubble(int *a)
{
    int limit = N-1;
    int leftPos = 0;
    do {
        leftPos = 0;
        for(int i=0;i<limit;i++)
        {
            if (a[i]>a[i+1])
            {
                swap(a[i],a[i+1]);
                leftPos = i;
            }
        }
        limit = leftPos;
    } while (leftPos);
}

// Алгоритм кучи
void sortHeapUp(int maxLevel, int *a)
{
    int i=maxLevel;
    while(i!=0)
    {
        int parent = i/2;
        if (a[i]>a[parent])
        {
            swap(a[i],a[parent]);
            i = parent;
        }
        else
            break;
    }
}

void sortHeapDown(int maxLevel, int *a)
{
    int i = 0;
    for(;;) {
        int child = 2*i;
        if (child>maxLevel) break;
        if (child+1 <= maxLevel)
        {
            if (a[child+1]>a[child]) child+=1;
        }
        if (a[i]<a[child])
        {
            swap(a[i],a[child]);
            i = child;
        }
        else
            break;
    }
}

void sortHeap(int *a)
{
    for(int i=1;i<N;i++)
    {
        sortHeapUp(i,a);
    }
    for(int i=N-1;i>0;i--)
    {
        swap(a[0],a[i]);
        sortHeapDown(i-1,a);
    }
}


// Алгоритм обмена
void sortExchange(int *a)
{
    for(int i=0;i<N;i++)
    {
        int smallest = i;
        for(int j=i+1;j<N;j++)
        {
            if (a[j]<a[smallest])
                smallest=j;
        }
        if (smallest>i) swap(a[i],a[smallest]);
    }
}

// Алгоритм ракушки
void sortShell(int *a)
{
    for(int offset = N/2; offset>0; offset/=2)
    {
        int maxPos;
        int limit=N-offset;
        do {
            maxPos = 0;
            for(int i=0;i<limit;i++)
            {
                if (a[i]>a[i+offset])
                {
                    swap(a[i],a[i+offset]);
                    maxPos = i;
                }
            }
            limit = maxPos-offset;
        } while(maxPos);
    }
}

// Алгоритм быстрой сортировки - fastest
void sortQuick(int low, int high, int *a)
{
    if (low<high)
    {
        if ((high-low)==1)
        {
            if (a[low]>a[high]) swap(a[low],a[high]);
        }
        else
        {
            int randIndex = randRange(low,high);
            swap(a[low],a[randIndex]);
            int part = a[high];
            int i,j;
            do {
                i=low; j=high;
                while (i<j && a[i]<=part) i++;
                while (j>i && a[j]>=part) j--;
                if (i<j) swap(a[i],a[j]);
            } while(i<j);
            swap(a[i],a[high]);
            if ((i-low)<(high-i))
            {
                sortQuick(low,i-1,a);
                sortQuick(i+1,high,a);
            }
            else
            {
                sortQuick(i+1,high,a);
                sortQuick(low,i-1,a);
            }
        }
    }
}


int main()
{
    srand(time(NULL));
    int list[N];
    int save[N];
    for(int i=0;i<N;i++)
    {
        list[i] = rand() % 100;
    }
    // save original array
    memcpy(save,list,sizeof(int)*N);
    showArray(list);
 
    sortInsertion(list);
    showArray(list);
    // restore original array
    memcpy(list,save,sizeof(int)*N);

    sortBubble(list);
    showArray(list);
    memcpy(list,save,sizeof(int)*N);

    sortHeap(list);
    showArray(list);
    memcpy(list,save,sizeof(int)*N);

    sortExchange(list);
    showArray(list);
    memcpy(list,save,sizeof(int)*N);

    sortShell(list);
    showArray(list);
    memcpy(list,save,sizeof(int)*N);

    sortQuick(0, N-1, list);
    showArray(list);
    
    return 1;
}


Есть также варианты на Паскале:

uses crt;

const N=20;

type
  TArray = array [1..N] of integer;

procedure show_array(a:TArray);
var i: integer;
begin
  for i:=1 to N do
    write(a[i]:4);
  writeln;
end;

procedure random_array(var a:TArray);
var i: integer;
begin
  for i:=1 to N do
    a[i]:=random(100);
end;

procedure swap(var a,b:integer);
var c:integer;
begin
  c:=a; a:=b; b:=c;
end;

procedure BubleSort(var a:TArray);
var i,count:integer;
    noswap:boolean;
begin
  count:=0;
  repeat
    noswap:=true;
    for i:=1 to N-1 do
      if a[i]>a[i+1] then
      begin
        swap(a[i],a[i+1]);
        count:=count+1;
        noswap:=false;
      end;
  until noswap;
  writeln('Count: ',count);
end;

procedure QuickBubleSort(var a:TArray);
var i,j,count:integer;
begin
  count:=0;
  for i:=1 to N-1 do
    for j:=i+1 to N do
      if a[j]<a[i] then
      begin
        swap(a[i],a[j]);
        count:=count+1;
      end;
  writeln('Count: ',count);
end;

procedure InsertSort(var a:TArray);
var i,j,k,count:integer;
begin
  count:=0;
  for i:=1 to N-1 do
  begin
    k:=i;
    for j:=i+1 to N do
      if a[k]>a[j] then
      begin
        k:=j; count:=count+1;
      end;
    swap(a[k], a[i]);
  end;
  writeln('Count: ',count);
end;

procedure QuickSort(var a:TArray; first,last:integer; var count: integer);
var l,r:integer;
begin
  l:=first; r:=last;
  repeat
    while (a[l]<=a[r]) and (l<r) do r:=r-1;
    if l<r then
    begin
      swap(a[l],a[r]);
      l:=l+1;
      count:=count+1;
    end;
    while (a[l]<=a[r]) and (l<r) do l:=l+1;
    if l<r then
    begin
      swap(a[l],a[r]);
      r:=r-1;
      count:=count+1;
    end;
  until l=r;
  if l-1>first then QuickSort(a,first,l-1,count);
  if last>r+1 then QuickSort(a,r+1,last,count);
end;

procedure MixSort(var a:TArray; first,last:integer; var count: integer);
var
    l,r,x:integer;
begin
  l:=first; r:=last; x:=a[(l+r) div 2];
  repeat
    while a[l]<x do l:=l+1;
    while x<a[r] do r:=r-1;
    if l<=r then
    begin
      swap(a[l],a[r]);
      l:=l+1; r:=r-1;
      count:=count+1;
    end;
  until l>r;
  if first<r then MixSort(a,first,r,count);
  if l<last then MixSort(a,l,last,count);
end;


var
  a,b: TArray;
  c:integer;
begin
  clrscr; randomize;
  random_array(a); show_array(a);
  b:=a;
  BubleSort(a); show_array(a);
  a:=b;
  QuickBubleSort(a); show_array(a);
  a:=b;
  InsertSort(a); show_array(a);
  a:=b; c:=0;
  QuickSort(a,1,N,c);
  writeln('Count: ',c);
  show_array(a);
  a:=b; c:=0;
  MixSort(a,1,N,c);
  writeln('Count: ',c);
  show_array(a);
  readkey;
end.