500. TSORT - Turbo Sort

Given the list of numbers, you are to sort them in non decreasing order.

Input.

t – the number of numbers in list, then t lines follow [t ≤ 10⁶].

Each line contains one integer: n [0 ≤ n ≤ 10⁶]

Output.

Output given numbers in non decreasing order.

Sample Input

5

5

3

6

7

1

Sample Output

1

3

5

6

7

РЕШЕНИЕ

сортировка

Анализ алгоритма

Воспользуемся любым алгоритмом сортировки.

Реализация алгоритма

Воспользуемся сортировкой STL.

#include <cstdio>

#include <algorithm>

#define MAX 1000001

using namespace std;

int i, n;

int m[MAX];

int main(void)

{

scanf("%d",&n);

for(i = 0; i < n; i++)

scanf("%d",&m[i]);

sort(m,m+n);

for(i = 0; i < n; i++)

printf("%d\n",m[i]);

return 0;

}

Динамическое выделение памяти

#include <cstdio>

#include <algorithm>

using namespace std;

int i, n;

int *m;

int main(void)

{

scanf("%d",&n);

m = new int[n];

for(i = 0; i < n; i++)

scanf("%d",&m[i]);

sort(m,m+n);

for(i = 0; i < n; i++)

printf("%d\n",m[i]);

delete[] m;

return 0;

}

Сортировка слиянием

#include <stdio.h>

#include <string.h>

int *m;

int n, i, j;

void merge(int *a, int aL, int aR, int bL, int bR)

{

// a[aL..aR] a[bL..bR] are merged into a[aL..bR]

int ptr = 0, Left = aL, len = bR - aL + 1;

int *temp = new int[len];

while((aL <= aR) && (bL <= bR))

temp[ptr++] = (a[aL] < a[bL]) ? a[aL++] : a[bL++];

while (aL <= aR) temp[ptr++] = a[aL++];

while (bL <= bR) temp[ptr++] = a[bL++];

memcpy(a + Left,temp,len*sizeof(int));

delete[] temp;

}

void mergeSort(int *a, int left, int right)

{

if (left < right)

{

int middle = (left + right) / 2;

mergeSort(a,left,middle);

mergeSort(a,middle+1,right);

merge(a, left, middle, middle + 1, right);

}

}

int main(void)

{

scanf("%d",&n);

m = new int[n];

for(i = 0; i < n; i++)

scanf("%d",&m[i]);

mergeSort(m, 0, n - 1);

for(i = 0; i < n; i++)

printf("%d\n",m[i]);

delete[] m;

return 0;

}

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

#include <stdio.h>

#include <string.h>

int *m;

int n, i, j;

void merge(int *a, int Left, int Middle, int Right)

{

// a[Lleft..Middle] -> res[]

// res[0..len-1] a[Middle+1..Right] are merged into a[Left..Right]

// we copy only half of array

int len = Middle++ - Left + 1, ptr = 0;

int *temp = new int[len];

memcpy(temp,a + Left,len*sizeof(int));

while((ptr < len) && (Middle <= Right))

a[Left++] = (temp[ptr] <= a[Middle]) ? temp[ptr++] : a[Middle++];

while (ptr < len) a[Left++] = temp[ptr++];

delete[] temp;

}

void mergeSort(int *a, int left, int right)

{

if (left < right)

{

int middle = (left + right) / 2;

mergeSort(a,left,middle);

mergeSort(a,middle+1,right);

merge(a, left, middle, right);

}

}

int main(void)

{

scanf("%d",&n);

m = new int[n];

for(i = 0; i < n; i++)

scanf("%d",&m[i]);

mergeSort(m, 0, n - 1);

for(i = 0; i < n; i++)

printf("%d\n",m[i]);

delete[] m;

return 0;

}

Быстрая сортировка

#include <stdio.h>

#include <string.h>

int *m;

int n, i, j;

int min(int i, int j)

{

return (i < j) ? i : j;

}

int max(int i, int j)

{

return (i > j) ? i : j;

}

void swap(int &i, int &j)

{

int temp = i; i = j; j = temp;

}

int Partition(int *m, int L, int R)

{

int x, i = L - 1, j = R + 1;

// pivot = median of three

int a = m[L], b = m[(L+R)/2], c = m[R];

x = a + b + c - min(min(a,b),c) - max(max(a,b),c);

while(1)

{

do j--; while (m[j] > x);

do i++; while (m[i] < x);

if (i < j) swap(m[i],m[j]); else return j;

}

}

void QuickSort(int *m, int L, int R)

{

int q;

if (L < R)

{

q = Partition(m, L, R);

QuickSort(m, L,q); QuickSort(m, q+1,R);

}

}

int main(void)

{

scanf("%d",&n);

m = new int[n];

for(i = 0; i < n; i++)

scanf("%d",&m[i]);

QuickSort(m,0,n-1);

for(i = 0; i < n; i++)

printf("%d\n",m[i]);

delete[] m;

return 0;

}

Быстрая сортировка – версия 2

#include <stdio.h>

#include <string.h>

int *m;

int n, i, j;

void swap(int &i, int &j)

{

int temp = i; i = j; j = temp;

}

int min(int i, int j)

{

return (i < j) ? i : j;

}

int max(int i, int j)

{

return (i > j) ? i : j;

}

int Partition(int *m, int L, int R)

{

int x, i = L, j = R;

// pivot = median of three

int a = m[L], b = m[(L+R)/2], c = m[R];

x = a + b + c - min(min(a,b),c) - max(max(a,b),c);

while (i <= j)

{

while (m[i] < x) i++;

while (m[j] > x) j--;

if (i <= j)

swap(m[i++],m[j--]);

}

return i;

}

void QuickSort(int *m, int L, int R)

{

int q;

if (L < R)

{

q = Partition(m, L, R);

QuickSort(m,L,q-1);

QuickSort(m,q,R);

}

}

int main(void)

{

scanf("%d",&n);

m = new int[n];

for(i = 0; i < n; i++)

scanf("%d",&m[i]);

QuickSort(m,0,n-1);

for(i = 0; i < n; i++)

printf("%d\n",m[i]);

delete[] m;

return 0;

}