2321. Сортировка

Отсортируйте массив целых чисел в порядке неубывания.

Вход. Первая строка содержит целое число n (1 ≤ n ≤ 1000). Вторая строка содержит n целых чисел, по модулю не превышающих 2·10⁹.

Выход. Вывести все n чисел в порядке неубывания.

Пример входа	Пример выхода
5 9 2 7 1 2	1 2 2 7 9

РЕШЕНИЕ

сортировка

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

Для сортировки целых чисел в неубывающем порядке достаточно воспользоваться любым алгоритмом сортировки. Или вызвать функцию sort библиотеки шаблонов STL.

Читаем входные данные в целочисленный массив. Сортируем массив. Выводим содержимое массива.

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

Входную последовательность целых чисел будем хранить в векторе v.

vector<int> v;

Читаем входные данные.

scanf("%d",&n);

v.resize(n);

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

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

Сортируем вектор v при помощи функции sort.

sort(v.begin(),v.end());

Выводим элементы вектора v в порядке неубывания.

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

printf("%d ",v[i]);

printf("\n");

Реализация алгоритма – STL sort, массив

Входную последовательность целых чисел будем хранить в массиве m.

#define MAX 1010

int m[MAX];

Читаем входные данные.

scanf("%d",&n);

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

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

Сортируем массив m при помощи функции sort.

sort(m,m+n);

Выводим элементы массива m в порядке неубывания.

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

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

printf("\n");

STL sort – компаратор

#include <cstdio>

#include <algorithm>

#define MAX 1010

using namespace std;

int m[MAX];

int i, n;

int f(int a, int b)

{

return a < b;

}

int main(void)

{

scanf("%d",&n);

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

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

sort(m,m+n,f);

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

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

printf("\n");

return 0;

}

Обменная Сортировка

#include <stdio.h>

#define MAX 1000

int m[MAX];

int i, n;

void sort(void)

{

int i, j, temp;

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

for(j = i + 1; j < n; j++)

if (m[i] > m[j])

{

temp = m[i];

m[i] = m[j];

m[j] = temp;

}

}

int main(void)

{

scanf("%d",&n);

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

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

sort();

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

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

printf("\n");

return 0;

}

Сортировка кучей

#include <stdio.h>

#define MAX 1001

int a[MAX];

int n;

int left(int i)

{

return 2 * i;

}

int right(int i)

{

return 2 * i + 1;

}

void swap(int &i, int &j)

{

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

}

// max - heap

void heapify(int a[], int i, int n) // n = size of a heap

{

int largest = 0;

int l = left(i);

int r = right(i);

if (l <= n && a[l] > a[i]) largest = l;

else largest = i;

if (r <= n && a[r] > a[largest]) largest = r;

if (largest != i)

{

swap(a[i], a[largest]);

heapify(a, largest, n);

}

}

void BuildHeap(int a[], int n)

{

for (int i = n / 2; i > 0; i--)

heapify(a, i, n);

}

void HeapSort(int a[], int n)

{

BuildHeap(a, n);

for (int i = n; i >= 2; i--)

{

swap(a[1], a[i]);

heapify(a, 1, i - 1);

}

}

int main(void)

{

scanf("%d", &n);

for (int i = 1; i <= n; i++)

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

HeapSort(a, n);

for (int i = 1; i <= n; i++)

printf("%d ", a[i]);

printf("\n");

return 0;

}

Сортировка кучей – STL

Читаем входные данные.

scanf("%d",&n);

v.resize(n);

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

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

Преобразуем массив чисел в кучу.

make_heap(v.begin(),v.end());

Удаление наибольшего элемента из кучи. Функция pop_heap меняет местами первый и последний элементы, уменьшает величину кучи на 1 и восстанавливает свойство кучи.

for(i = v.size(); i > 0; i--)

pop_heap(v.begin(),v.begin() + i);

Выводим отсортированный массив.

for(i = 0; i < v.size(); i++)

printf("%d ",v[i]);

printf("\n");

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

Сортирующий массив храним в массиве m.

int m[1010];

Перестановка пары элементов массива m.

void swap(int &i, int &j)

{

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

}

В качестве опорного выбираем самый левый элемент m[L]. Разделяем массив.

int Partition(int L, int R)

{

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

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;

}

}

Быстрая сортировка подмассива m[L..R].

void QuickSort(int L, int R)

{

int q;

if (L < R)

{

q = Partition(L, R);

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

}

}

Основная часть программы.

scanf("%d",&n);

for(i = 0; i < n; i++) scanf("%d",&m[i]);

QuickSort(0,n-1);

printf("%d",m[0]);

for(i = 1; i < n; i++) printf(" %d",m[i]);

printf("\n");

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

#include <stdio.h>

#include <string.h>

int i, n;

class Array

{

public:

int *m;

int size;

Array(int size = 0) : size(size)

{

m = new int[size];

}

int& operator[](int i)

{

return m[i];

}

~Array(void)

{

delete[] m;

}

void merge(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++] = (m[aL] < m[bL]) ? m[aL++] : m[bL++];

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

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

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

delete[] temp;

}

void Sort(void)

{

Sort(0,size - 1);

}

void Sort(int left, int right)

{

if (left < right)

{

int middle = (left + right) / 2;

Sort(left,middle);

Sort(middle+1,right);

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

}

}

};

int main(void)

{

scanf("%d",&n);

Array a(n);

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

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

a.Sort();

printf("%d",a[0]);

for(i = 1; i < n; i++) printf(" %d",a[i]);

printf("\n");

return 0;

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m[] = new int[n];

for(int i = 0; i < n; i++) m[i] = con.nextInt();

Arrays.sort(m);

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

System.out.print(m[i] + " ");

System.out.println();

con.close();

}

}

Java компаратор

import java.util.*;

class f implements Comparator<Integer>

{

// a < b means a - b < 0

public int compare(Integer a, Integer b)

{

return a - b;

}

}

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

Integer m[] = new Integer[n];

for(int i = 0; i < n; i++) m[i] = con.nextInt();

Arrays.sort(m, new f());

for(int i = 0; i < n; i++) System.out.print(m[i] + " ");

System.out.println();

con.close();

}

}

Java – сортировка кучей

import java.util.*;

public class Main

{

static int left(int i)

{

return 2 * i;

}

static int right(int i)

{

return 2 * i + 1;

}

static void swap(int a[], int i, int j)

{

int temp = a[i]; a[i] = a[j]; a[j] = temp;

}

//max - heap

static void heapify(int a[], int i, int n) // n = size of a heap

{

int largest = 0;

int l = left(i);

int r = right(i);

if (l <= n && a[l] > a[i]) largest = l;

else largest = i;

if (r <= n && a[r] > a[largest]) largest = r;

if (largest != i)

{

swap(a, i, largest);

heapify(a, largest, n);

}

}

static void BuildHeap(int a[], int n)

{

for (int i = n / 2; i > 0; i--)

heapify(a, i, n);

}

static void HeapSort(int a[], int n)

{

BuildHeap(a, n);

for (int i = n; i >= 2; i--)

{

swap(a, 1, i);

heapify(a, 1, i - 1);

}

}

public static void main(String[] args) {

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m[] = new int[n+1];

for(int i = 1; i <= n; i++)

m[i] = con.nextInt();

HeapSort(m, n);

for(int i = 1; i <= n; i++)

System.out.print(m[i] + " ");

System.out.println();

con.close();

}

}

Java – обменная сортировка

import java.util.*;

public class Main

{

static void sort(int m[])

{

for(int i = 0; i < m.length; i++)

for(int j = i + 1; j < m.length; j++)

if (m[i] > m[j])

{

int temp = m[i];

m[i] = m[j];

m[j] = temp;

}

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m[] = new int[n];

for(int i = 0; i < n; i++) m[i] = con.nextInt();

sort(m);

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

System.out.print(m[i] + " ");

con.close();

}

}

Java – быстрая сортировка

import java.util.*;

public class Main

{

public static int Partition (int[] A, int L, int R)

{

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

while(true)

{

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

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

if (i < j)

{

int temp = A[i];

A[i] = A[j];

A[j] = temp;

}

else return j;

}

}

public static void Qsort(int[] A, int L, int R)

{

if (L < R)

{

int q = Partition(A, L,R);

Qsort(A, L, q);

Qsort(A, q+1, R);

}

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m[] = new int[n];

for(int i = 0; i < n; i++) m[i] = con.nextInt();

Qsort(m,0,n-1);

for(int i = 0; i < n - 1; i++)

System.out.print(m[i] + " ");

System.out.println(m[n-1]);

}

}

Java – динамический массив

import java.util.*;

public class Main

{

public static class DynamicArray

{

private int[] storage;

private int size;

public DynamicArray()

{

storage = new int[100];

size = 0;

}

public DynamicArray(int capacity)

{

storage = new int[capacity];

size = 0;

}

public int length()

{

return size;

}

public void Print()

{

if (size == 0) return;

for(int i = 0; i < size - 1; i++)

System.out.print(storage[i]+ " ");

System.out.println(storage[size-1]);

}

public void ensureCapacity(int minCapacity)

{

int capacity = storage.length;

if (minCapacity > capacity)

{

int newCapacity = (capacity * 3) / 2 + 1;

if (newCapacity < minCapacity) newCapacity = minCapacity;

int temp[] = new int[newCapacity];

System.arraycopy(storage, 0, temp, 0, capacity);

storage = temp;

//storage = Arrays.copyOf(storage, newCapacity);

}

}

private void pack()

{

int capacity = storage.length;

if (size <= capacity / 2)

{

int newCapacity = (size * 3) / 2 + 1;

int temp[] = new int[newCapacity];

System.arraycopy(storage, 0, temp, 0, capacity);

storage = temp;

//storage = Arrays.copyOf(storage, newCapacity);

}

}

public void trim()

{

int newCapacity = size;

int temp[] = new int[newCapacity];

System.arraycopy(storage, 0, temp, 0, storage.length);

storage = temp;

//storage = Arrays.copyOf(storage, newCapacity);

}

private void rangeCheck(int index)

{

if (index < 0 || index >= size)

throw new IndexOutOfBoundsException

("Index: " + index + ", Size: " + size);

}

public void set(int index, int value)

{

rangeCheck(index);

storage[index] = value;

}

public int get(int index)

{

rangeCheck(index);

return storage[index];

}

public void removeAt(int index)

{

rangeCheck(index);

int moveCount = size - index - 1;

if (moveCount > 0)

System.arraycopy(storage, index + 1, storage,

index, moveCount);

size--;

pack();

}

public void insertAt(int index, int value)

{

if (index < 0 || index > size)

throw new IndexOutOfBoundsException

("Index: " + index + ", Size: " + size);

ensureCapacity(size + 1);

int moveCount = size - index;

if (moveCount > 0)

System.arraycopy(storage, index, storage,

index + 1, moveCount);

storage[index] = value;

size++;

}

public void push_back(int value)

{

ensureCapacity(size + 1);

storage[size] = value;

size++;

}

public void Sort()

{

Arrays.sort(storage,0,size);

}

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

DynamicArray m = new DynamicArray(1);

for(int i = 0; i < n; i++) m.push_back(con.nextInt());

m.Sort(); m.Print();

}

}

Python реализация

n = int(input())

lst = list(map(int,input().split()))

lst.sort()

print(*lst)

Python реализация – sorted

n = int(input())

lst = map(int, input().split())

lst = sorted(lst)

for i in range(n):

print(lst[i], end=" ")

print()

Python реализация – сортировка кучей

def heapify(lst, n, i): # n is size of heap

largest = 0

l = 2 * i # left = 2*i

r = 2 * i + 1 # right = 2*i + 1

if l <= n and lst[l] > lst[i]: largest = l

else: largest = i

if r <= n and lst[r] > lst[largest]: largest = r

if largest != i:

lst[i], lst[largest] = lst[largest], lst[i] # swap

heapify(lst, n, largest)

def BuildHeap(lst, n):

for i in range(n // 2, 0, -1):

heapify(lst, n, i)

def heapSort(lst, n):

BuildHeap(lst, n)

for i in range(n, 1, -1):

lst[i], lst[1] = lst[1], lst[i] # swap

heapify(lst, i - 1, 1)

n = int(input())

lst = list(map(int,input().split()))

lst = [0] + lst

heapSort(lst, n)

for i in range(1,n+1):

print(lst[i], end = " ")