[백준 10989] 수정렬하기 feat. Quick Sort VS Counting Sort 비교

 *QuickSort 버전*

#include <iostream>

#include <string>

using namespace std;

void swap(int arr[], int a, int b)

{

    int temp = arr[a];

    arr[a] = arr[b];

    arr[b] = temp;

}

int partition(int arr[], int left, int right)

{

    int pivot = arr[left];

    int low = left + 1;

    int high = right;

    

    while(low <= high)

    {

        while(low <= right && pivot >= arr[low])

            low++;

        

        while(high >= left+1 && pivot <= arr[high])

            high--;

        

        if(low <= high)

        {

            swap(arr, low, high);

        }

    }

    

    swap(arr, left, high);

    

    return high;

}

void quickSort(int arr[], int left, int right)

{

    if(left <= right)

    {

        int pivot = partition(arr, left, right);

        quickSort(arr, left, pivot-1);

        quickSort(arr, pivot+1, right);

    }

}

int main(int argc, const char * argv[]) {

    int n;

    cin >> n;

    

    int * arr = new int[n];

    

    for (int i = 0; i < n; i++)

    {

        cin >> arr[i];

    }

    

    quickSort(arr, 0, n-1);

    

    for (int i = 0; i < n; i++)

        cout << arr[i] << endl;

}

런타임에러가 난다. 더 빠른 알고리즘이 필요하다.

*Counting Sort 버전*


#include<iostream>

using namespace std;

int cnt[10001];

int main()

{

    int n;

    cin >> n;

    

    for(int i=0; i<n; i++)

    {

        int input;

        cin >> input;

        cnt[input]++;

    }

    

    for(int i=1; i<=10000; i++)

    {

        if(cnt[i] >0)

            for(int j=0; j<cnt[i]; j++)

                printf("%d\n",i);

    }

    

    

    return 0;

}

Array Sorting Algorithms

Algorithm	Time Complexity			Space Complexity
	Best	Average	Worst	Worst
Quicksort	Ω(n log(n))	Θ(n log(n))	O(n^2)	O(log(n))
Mergesort	Ω(n log(n))	Θ(n log(n))	O(n log(n))	O(n)
Timsort	Ω(n)	Θ(n log(n))	O(n log(n))	O(n)
Heapsort	Ω(n log(n))	Θ(n log(n))	O(n log(n))	O(1)
Bubble Sort	Ω(n)	Θ(n^2)	O(n^2)	O(1)
Insertion Sort	Ω(n)	Θ(n^2)	O(n^2)	O(1)
Selection Sort	Ω(n^2)	Θ(n^2)	O(n^2)	O(1)
Tree Sort	Ω(n log(n))	Θ(n log(n))	O(n^2)	O(n)
Shell Sort	Ω(n log(n))	Θ(n(log(n))^2)	O(n(log(n))^2)	O(1)
Bucket Sort	Ω(n+k)	Θ(n+k)	O(n^2)	O(n)
Radix Sort	Ω(nk)	Θ(nk)	O(nk)	O(n+k)
Counting Sort	Ω(n+k)	Θ(n+k)	O(n+k)	O(k)
Cubesort	Ω(n)	Θ(n log(n))	O(n log(n))	O(n)