Сортировка (#2321)

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

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

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

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

Входной массив целых чисел будем хранить в векторе 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 – массивы

#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 – компаратор

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

        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 || 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```java
                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=" ")
print()