Sıralama (#2321)

Alqoritm Analizi

Tam sıralı olmayan ardıcıllıqda tam ədədləri sıralamaq üçün hər hansı bir sıralama alqoritmindən istifadə etmək kifayətdir. Və ya STL şablon kitabxanasının sort funksiyasını çağırın.

Giriş məlumatlarını tam ədəd massivinə oxuyuruq. Massivi sıralayın. Massivin məzmununu çap edin.

Alqoritm Tətbiqi

Tam ədədlərin giriş massivi v vektorunda saxlanılacaq.

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 - Massivlər

#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 - Müqayisəçi

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

Mübadilə Sıralaması

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

Yığın Sıralaması

#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 - yığın
void heapify(int a[], int i, int n) // n = yığın ölçüsü
{
    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;
}

Yığın Sıralaması – STL

Giriş məlumatlarını oxuyun.

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

Ədədlər massivini yığın halına çevirin.

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

Yığından ən böyük elementi çıxarın. pop_heap funksiyası ilk və son elementləri dəyişdirir, yığının ölçüsünü 1 azaldır və yığın xüsusiyyətini bərpa edir.

for (i = v.size(); i > 0; i--)
    pop_heap(v.begin(), v.begin() + i);

Sıralanmış massivi çap edin.

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

Tez Sıralama

Sıralanacaq massiv m massivində saxlanılır.

int m[1010];

Massivdə m çift elementləri yerini dəyişir.

void swap(int &i, int &j)
{
    int temp = i; i = j; j = temp;
}

Sol ən kiçik element m[L] pivot kimi seçilir. Massivi bölmək.

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

Alt massivi m[L..R] tez sıralama.

void QuickSort(int L, int R)
{
    int q;
    if (L < R)
    {
        q = Partition(L, R);
        QuickSort(L,q); QuickSort(q+1,R);
    }
}

Proqramın əsas hissəsi.

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

Birləşdirmə Sıralaması + Siniflər

#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 Tətbiqi

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 Müqayisəçi

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 - Yığın Sıralaması

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 - yığın
    static void heapify(int a[], int i, int n) // n = yığın ölçüsü
    {
        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 - Mübadilə Sıralaması

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 - Tez Sıralama

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 - Dinamik Massiv

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 Tətbiqi

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

Python Tətbiqi – sorted

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

lst = sorted(lst)

for i in range(n):
    print(lst[i], end=" ")
print()

Python Tətbiqi – Yığın Sıralaması

def heapify(lst, n, i): # n yığının ölçüsüdür
    largest = 0
    l = 2 * i      # sol = 2*i
    r = 2 * i + 1  # sağ = 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]  # dəyişdir
        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]  # dəyişdir
    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()