Sort an array of integers in non-decreasing order.
Input. The
first line contains an integer n (1
≤ n ≤ 1000). The second
line contains n integers, each not
exceeding 2 * 109
in absolute value.
Output. Print the n integers of
the array in non-decreasing order.
|
Sample
input |
Sample
output |
|
5 9 2 7 1 2 |
1 2 2 7 9 |
sort
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 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;
}
}
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;
}
Algorithm implementation – Heap Sort, STL
To work with heap, include
#include <algorithm>
Read the input data.
scanf("%d",&n);
v.resize(n);
for(i = 0; i < n; i++)
scanf("%d",&v[i]);
Transform the array of numbers into the heap.
make_heap(v.begin(),v.end());
Delete the maximum element
from the heap. Function pop_heap swaps the first and last
elements, decrease 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");
Algorithm implementation – Quick Sort
We store integers in the
array m.
int m[1010];
Swap two elements.
void swap(int &i, int &j)
{
int temp = i;
i = j; j = temp;
}
Choose as a pivot the leftmost element m[L]. Partition 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 sort of 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);
}
}
The 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");
Java implementation
import
java.util.*;
public class
{
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 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 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 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 implementation
– Quick Sort
import
java.util.*;
public class
{
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 implementation
– dynamic array
import
java.util.*;
public class
{
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 implementation
Read the input data.
n = int(input())
lst = list(map(int,input().split()))
Sort the list lst 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 lst 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 = " ")