Sorting (Editorial)

To sort integers in non-decreasing order, we can use any sorting algorithm or call the sort function from the Standard Template Library (STL).

Read the input data into an integer array. Sort the array. Print the contents of the array.

Algorithm implementation

The input sequence of integers is stored in the vector $v$ .

vector<int> v;

Read the input data.

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

Sort the vector $v$ using the sort function.

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

Print the elements of the vector $v$ in non-decreasing order.

for (i = 0; i < n; i++) 
  printf("%d ",v[i]);
printf("\n");

Algorithm implementation — STL sort, array

The input sequence of integers is stored in the array $m$ .

#define MAX 1010
int m[MAX];

Read the input data.

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

Sort the array $m$ using the sort function.

sort(m, m + n);

Print the elements of the array $m$ in non-decreasing order.

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

Algorithm implementation — STL sort, comparator

The input sequence of integers is stored in the array $m$ .

#define MAX 1010
int m[MAX];

The function f is used as a comparator for sorting the elements of the array in ascending order.

int f(int a, int b)
{
  return a < b;
}

Read the input data.

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

Sort the array $m$ using the sort function.

sort (m, m + n, f);

Print the elements of the array $m$ in non-decreasing order.

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

Algorithm implementation — Swap Sort

Swap sort is a simple sorting algorithm that repeatedly iterates through the array, swapping adjacent elements if they are in the wrong order.

Start by iterating through the array from the beginning to the end.
Compare each pair of adjacent elements.
If the elements are in the wrong order (e.g., the element at index $i$ is greater than the element at index $i + 1$ i + 1 for ascending order), swap them.
Continue this process until no more swaps are needed.
Repeat this process until the entire array is sorted.

The input sequence of integers is stored in the array $m$ .

#define MAX 1000
int m[MAX];

The function sort implements sorting of the array $m$ in ascending order using swap sort.

void sort(void)
{
  for (int i = 0; i < n; i++)
  for (int j = i + 1; j < n; j++)
    if (m[i] > m[j])
    {
      int temp = m[i];
      m[i] = m[j];
      m[j] = temp;
    }
}

C++

Read the input data.

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

Sort the array $m$ .

sort();

Print the elements of the array $m$ in non-decreasing order.

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

Algorithm implementation — Heap Sort

#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;
}

C++

Algorithm implementation — Heap Sort, 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;
  }
}

C++

Быстрая сортировка подмассива $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);
  }
}

C++

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

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");

Java implementation

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

Java implementation — comparator

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

Java implementation — heap sort

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

Java implementation — swap sort

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

Java implementation — Quick Sort

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

Python implementation

Read the input data.

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

Sort the list $l s t$ using the sort function.

lst.sort()

Print the sorted list.

print(*lst)

Python implementation — sorted

Read the input data.

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

Sort the list $l s t$ using the sorted function.

lst = sorted(lst)

Print the sorted list.

print(*lst)

Python implementation — heap sort

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 = " ")

Python