Algorithm Analysis
To sort integers in non-decreasing order, it is sufficient to use any sorting algorithm. Or call the sort function of the STL template library.
We read the input data into an integer array. Sort the array. Print the contents of the array.
Algorithm Implementation
The input array of integers will be stored in the vector v.
vector<int> v;
scanf("%d", &n);
v.resize(n);
for (i = 0; i < n; i++)
scanf("%d", &v[i]);
sort(v.begin(), v.end());
for (i = 0; i < n; i++)
printf("%d ", v[i]);
printf("\n");STL sort – Arrays
#include <cstdio>
#include <algorithm>
#define MAX 1010
using namespace std;
int m[MAX];
int i, n;
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 ", m[i]);
printf("\n");
return 0;
}STL sort – Comparator
#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;
}Exchange Sorting
#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;
}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;
}Heap Sort – STL
Read the input data.
scanf("%d", &n);
v.resize(n);
for (i = 0; i < n; i++)
scanf("%d", &v[i]);Convert the array of numbers into a heap.
make_heap(v.begin(), v.end());
Removing the largest element from the heap. The function pop_heap swaps the first and last elements, decreases the size of the heap by 1, and restores the heap property.
for (i = v.size(); i > 0; i--)
pop_heap(v.begin(), v.begin() + i);Print the sorted array.
for (i = 0; i < v.size(); i++)
printf("%d ", v[i]);
printf("\n");Quick Sort
The sorting array is stored in the array m.
int m[1010];
Swapping a pair of elements in the array m.
void swap(int &i, int &j)
{
int temp = i; i = j; j = temp;
}Selecting the leftmost element m[L] as the pivot. Partitioning the array.
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;
}
}Quick sorting the subarray 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);
}
}Main part of the program.
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");Merge Sort + Classes
#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 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 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 – 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 – Exchange Sorting
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 – 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 – Dynamic Array
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;
}
}
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;
}
}
public void trim()
{
int newCapacity = size;
int temp[] = new int[newCapacity];
System.arraycopy(storage, 0, temp, 0, storage.length);
storage = temp;
}
private void rangeCheck(int index)
{
if (index < 0 or 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 Implementation
n = int(input()) lst = list(map(int, input().split())) lst.sort() print(*lst)
Python Implementation – sorted
n = int(input())
lst = map(int, input().split())
lst = sorted(lst)
for i in range(n):
print(lst[i], end=" ")
print()Python Implementation – Heap Sort
def heapify(lst, n, i): # n is size of a 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):
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=" ")
print()