Sort

 

종류	특징	시간복잡도
선택정렬	가장 작은 값을 앞으로
버블정렬	앞부분 두개씩 비교
삽입정렬	필요할 때만 위치 변경
퀵정렬	분할정복 Pivot을 기준으로 Divide low와 high가 엇가리면 위치를 변경 Pivot에 따라 편향 가능성이 존재 C++의 sort가 이 방법을 사용, sort의 경우 시간복잡도가 최악의 경우가 되는 경우를 방지	최선 최악
병합정렬	분할정복 나누고 합치기 합칠때는 2의 배수씩 합친다 nlogn의 시간복잡도를 보장
힙정렬	Heap Tree Node 구조 힙정렬 -> 힙구조 반복 maxHeap - parentNode > child Node - minHeap - child Node > parentNode -
계수정렬 (Counting Sort)	범위조건이 존재할 때만 사용 중복되는 숫자가 존재할 경우 시간복잡도와 공간복잡도를 획기적으로 줄일 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/*Heap Sort*/
// maxHeap
void maxHeapInit(vector<int> &data, int dataSize)
{
    for (int i = 1; i < dataSize; i++)
    {
        int child = i;
        do
        {
            int root = (child - 1) / 2;
            if (data[root] < data[child])
                swap(data[root], data[child]);
            child = root;
        } while (child != 0);
    }
}

// minHeap
void minHeapInit(vector<int> &data, int dataSize)
{
    for (int i = 1; i < dataSize; i++)
    {
        int child = i;
        do
        {
            int root = (child - 1) / 2;
            if (data[root] > data[child])
                swap(data[root], data[child]);
            child = root;
        } while (child != 0);
    }
}

void heapSort(vector<int> &data, int dataSize)
{
    maxHeapInit(data, data.size());
    for (int i = dataSize - 1; i >= 0; i--)
    {
        swap(data[0], data[i]);
        maxHeapInit(data, i);
    }
}

int main()
{
    int N;
    vector<int> data;
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int tmp;
        cin >> tmp;
        data.push_back(tmp);
    }

    heapSort(data, data.size());

    for (int i = 0; i < data.size(); i++)
        cout << data[i] << endl;
}

#include <iostream>
#include <vector>

using namespace std;

int N, arr[1000001];
int *sorted;

void merge(int left, int right)
{
    int mid = (left + right) / 2;
    int i = left;
    int j = mid + 1;
    int k = left;

    while (i <= mid && j <= right)
    {
        if (arr[i] <= arr[j])
            sorted[k++] = arr[i++];
        else
            sorted[k++] = arr[j++];
    }

    int temp = i > mid ? j : i;

    while (k <= right)
        sorted[k++] = arr[temp++];
    for (int i = left; i <= right; i++)
        arr[i] = sorted[i];
}

void partition(int left, int right)
{
    int mid;
    if (left < right)
    {
        mid = (left + right) / 2;
        partition(left, mid);
        partition(mid + 1, right);
        merge(left, right);
    }
}

int main()
{
    int N;
    cin >> N;
    sorted = new int[N];

    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);

    partition(0, N - 1);

    for (int i = 0; i < N; i++)
        cout << arr[i] << '\n';
}

#include <iostream>
#include <vector>

using namespace std;

void quickSort(int *data, int start, int end) {
  if (start >= end) return;
  int pivot = start;  // 기준 값
  int i = start + 1;
  int j = end;

  while (i <= j) {
    while (data[i] <= data[pivot])
      i++;
    while (data[j] >= data[pivot] && j > start)  // 키 값보다 작은 값 만날 때까지 왼쪽으로 이동
      j--;
    if (i > j)  //현재 엇갈린 상태면 pivot 값 교체
    {
      int temp = data[j];
      data[j] = data[pivot];
      data[pivot] = temp;
    } else {
      int temp = data[j];
      data[j] = data[i];
      data[i] = temp;
    }
    // 재귀 호출
    quickSort(data, start, j - 1);
    quickSort(data, j + 1, end);
  }
}

int main() {
  int data[7] = {38,27,43,9,3,82,10};
  int len = 7;
  quickSort(data, 0, len - 1);

  for (int i = 0; i < len; i++) cout << data[i] << ' ';

  return 0;
}