Quick Sorting & Hash function

1. Describe linear median finding algorithm, Show that its time complexity is Θ(n)

일반적인 quick sort의 시간 복잡도는 최선일 때 O(nlogn)이고, 최악일 때 O(n^2)만큼 걸린다.

수열의 길이가 n일 때 알고리즘의 수행 시간의 기댓값을 T(n)이라고 하자. 수열이 a1, ... , an으로 주어졌을 때, 이를 오름차순으로 정렬한 것을 b1, ... , bn이라고 하면 {a1, ... , an} = {b1, ... , bn}고, b1 < ... < bn 이다. 만약 알고리즘이 단계 2에서 x = b_j+1을 골랐다고 하자. 그러면 |A < x| = j이고 |A ≥ x| = n − j가 된다. 따라서 다음 재귀 호출에서 살아 남는 수열은 아무리 길어도 j 와 n − j 중 최댓값을 넘지 못한다.

따라서 j가 만약 n/4 ≤ j ≤ 3n/4라면 수열의 길이는 아무리 길어도 3n/4을 넘지 못한다. 균등한 확률로 j를 골랐으므로 j가 해당 조건을 만족할 확률은 1/2입니다. 반대의 경우에는 수열의 길이가 n을 넘지는 않는다는 내용이 성립하므로 아래의 점화식을 세울 수 있다.

Inductive Proof

T(n) = 1/2*T(3n/4) + 1/2*T(n) + O(n)

T(n) = cn

cn = 1/2*3cn/4 + cn/2 + O(n)

O(n) = 1/8n이므로, T(n) = O(n)이다.

 

2. In hashing function, why the coefficient a should not be 0?

해시 함수 식 h(p, m) = ((ak + b) mod p) mod m에서 a가 0이 되면 해시 함수 키 값에 상관없이 항상 (b mod p) mod m을 반환하기 때문에 충돌 가능성이 커진다. 따라서 a를 0으로 설정하지 않고 최소 1이상의 적절한 값을 선택해 해시 함수를 구현하는 것이 좋으며, 해시 함수를 더 균등하게 분포시켜 충돌 발생 확률을 낮춰야 한다.

3. Read chapter 8.4. Solve example 8.1 in the chapter.

n개의 키가 m개의 바구니에 균일하게 분포되어 있다면 실패한 검색에서 비교 횟수는 n/m이다. 여기서 만약 키가 균일하게 분포돼 있고 n = 2m이라면, 실패한 검색은 2m/m = 2번의 비교가 필요하다. 따라서, 성공한 검색은 평균 비교 횟수가 2m/2m + 1/2 = 3/2가 된다.

하지만 이 예시는 키가 균일하게 분포된 경우이고, 그렇지 않은 경우도 발생할 수 있다. (ex. 키가 하나의 바구니에 몰리게 되는 경우도 발생할 수 있다.) 그런 경우 각 키가 서로 다른 바구니로 각각 해시될 확률이 거의 같다고 가정하면, 한 개의 바구니에 최소한 k개 키가 들어있을 확률은 nCk * (1/m)^(k)보다 작거나 같다. 여기서 (1/m)^k은 어떤 특정한 k개의 키 조합이 바구니에 들어갈 확률이다. 

Birthday dataset

Approach 1. unordered array using set

Time Complexity: n

In-place: in-place

Stable: stable

// unordered array using set
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int cnt = 0;
    int n, birthday, find, min;
    double p;

    vector <int> contain;
    vector <int> v;

    ifstream fp("birthday.txt");

    if (fp.is_open()) {
        fp >> n;
        for (int i = 0; i < n; i++) {
            int birthday;
            fp >> birthday;
            v.push_back(birthday);
        }
    }
    else {
        cout << "no file exist" << endl;
    }

    for (int i = 0; i < v.size(); i++) { // ---> O(n)
        auto it = std::find(v.begin() + (i+1), v.end(), v[i]);
        if (it != v.end()) {
            contain.push_back(v[i]);
            cnt += 1;
        }

    }

    p = 1 - pow(double(364 / 365), (n * (n - 1) / 2));

    cout << "96명 중 두 사람이 동일한 생일을 가질 확률: " << p * 100 << "%" << endl;

    if (cnt == 0) {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << '0' << endl;
    }
    else {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << cnt << endl;
        cout << "동일한 생일을 가진 쌍의 날짜:" << endl;
        for (int i = 0; i < contain.size(); i++) {
            cout << contain[i] << endl;
        }

    }

    fp.close();

}

 

Approach 2. Quick Sorting

Time Complexity: nlogn

In-place: in-place

Stable: unstable

1. Basic quick sort

pivot: quick[0]인 경우

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;

void quickSort(vector<int>& quick, int i, int j);

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int cnt = 0;
    int n, birthday, find, min;
    double p;

    vector <int> contain;
    vector <int> quick;

    ifstream fp("birthday.txt");

    if (fp.is_open()) {
        fp >> n;
        for (int i = 0; i < n; i++) {
            int birthday;
            fp >> birthday;
            quick.push_back(birthday);
        }
    }
    else {
        cout << "no file exist" << endl;
    }

    quickSort(quick, 0, n - 1);

    for (int i = 1; i < quick.size(); i++) {
        if (quick[i - 1] == quick[i]) {
            contain.push_back(quick[i]);
            cnt += 1;
        }

    }

    p = 1 - pow(double(364 / 365), (n * (n - 1) / 2));

    cout << "96명 중 두 사람이 동일한 생일을 가질 확률: " << p * 100 << "%" << endl;

    if (cnt == 0) {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << '0' << endl;
    }
    else {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << cnt << endl;
        cout << "동일한 생일을 가진 쌍의 날짜:" << endl;
        for (int i = 0; i < contain.size(); i++) {
            cout << contain[i] << endl;
        }

    }

    fp.close();

}

void quickSort(vector<int>& quick, int i, int j)
{
    if (i >= j) return;
    int pivot = quick[i]; // -> pivot 왼쪽: quick[0]
    int left = i;
    int right = j;

    while (left <= right)
    {
        while (quick[left] < pivot) left++;
        while (quick[right] > pivot) right--;
        if (left <= right)
        {
            swap(quick[left], quick[right]);
            left++; right--;
        }
    }
    quickSort(quick, i, right);
    quickSort(quick, left, j);
}

pivot: quick[n-1]인 경우

// pivot 양, 끝으로
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;

void quickSort(vector<int>& quick, int i, int j);

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int cnt = 0;
    int n, birthday, find, min;
    double p;

    vector <int> contain;
    vector <int> quick;

    ifstream fp("birthday.txt");

    if (fp.is_open()) {
        fp >> n;
        for (int i = 0; i < n; i++) {
            int birthday;
            fp >> birthday;
            quick.push_back(birthday);
        }
    }
    else {
        cout << "no file exist" << endl;
    }

    quickSort(quick, 0, n - 1);

    for (int i = 1; i < quick.size(); i++) {
        if (quick[i - 1] == quick[i]) {
            contain.push_back(quick[i]);
            cnt += 1;
        }

    }

    p = 1 - pow(double(364 / 365), (n * (n - 1) / 2));

    cout << "96명 중 두 사람이 동일한 생일을 가질 확률: " << p * 100 << "%" << endl;

    if (cnt == 0) {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << '0' << endl;
    }
    else {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << cnt << endl;
        cout << "동일한 생일을 가진 쌍의 날짜:" << endl;
        for (int i = 0; i < contain.size(); i++) {
            cout << contain[i] << endl;
        }

    }

    fp.close();

}

void quickSort(vector<int>& quick, int i, int j)
{
    if (i >= j) return;
    int pivot = quick[j]; // -> pivot 오른쪽: quick[n-1]
    int left = i;
    int right = j;

    while (left <= right)
    {
        while (quick[left] < pivot) left++;
        while (quick[right] > pivot) right--;
        if (left <= right)
        {
            swap(quick[left], quick[right]);
            left++; right--;
        }
    }
    quickSort(quick, i, right);
    quickSort(quick, left, j);
}

 

2. Intelligent quick sort

pivot: quick[(n-1) / 2]인 경우

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;

void quickSort(vector<int>& quick, int i, int j);

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int cnt = 0;
    int n, birthday, find, min;
    double p;

    vector <int> contain;
    vector <int> quick;

    ifstream fp("birthday.txt");

    if (fp.is_open()) {
        fp >> n;
        for (int i = 0; i < n; i++) {
            int birthday;
            fp >> birthday;
            quick.push_back(birthday);
        }
    }
    else {
        cout << "no file exist" << endl;
    }

    quickSort(quick, 0, n - 1);

    for (int i = 1; i < quick.size(); i++) {
        if (quick[i-1] == quick[i]) {
            contain.push_back(quick[i]);
            cnt += 1;
        }

    }

    p = 1 - pow(double(364 / 365), (n * (n - 1) / 2));

    cout << "96명 중 두 사람이 동일한 생일을 가질 확률: " << p * 100 << "%" << endl;

    if (cnt == 0) {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << '0' << endl;
    }
    else {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << cnt << endl;
        cout << "동일한 생일을 가진 쌍의 날짜:" << endl;
        for (int i = 0; i < contain.size(); i++) {
            cout << contain[i] << endl;
        }

    }

    fp.close();

}

void quickSort(vector<int> &quick, int i, int j)
{
    if (i >= j) return;
    int pivot = quick[(i + j) / 2];
    int left = i;
    int right = j;

    while (left <= right)
    {
        while (quick[left] < pivot) left++;
        while (quick[right] > pivot) right--;
        if (left <= right)
        {
            swap(quick[left], quick[right]);
            left++; right--;
        }
    }
    quickSort(quick, i, right);
    quickSort(quick, left, j);
}

 

3. Paranoid quick sort

pivot을 랜덤하게 설정할 경우

#include <iostream>
#include <ctime>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;

void quickSort(vector<int>& quick, int i, int j);

int main() {

    srand(time(NULL)); // 항상 random한 수가 나오도록 설정
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int cnt = 0;
    int n, birthday, find, min;
    double p;

    vector <int> contain;
    vector <int> quick;

    ifstream fp("birthday.txt");

    if (fp.is_open()) {
        fp >> n;
        for (int i = 0; i < n; i++) {
            int birthday;
            fp >> birthday;
            quick.push_back(birthday);
        }
    }
    else {
        cout << "no file exist" << endl;
    }

    quickSort(quick, 0, n - 1);

    for (int i = 1; i < quick.size(); i++) {
        if (quick[i - 1] == quick[i]) {
            contain.push_back(quick[i]);
            cnt += 1;
        }

    }

    p = 1 - pow(double(364 / 365), (n * (n - 1) / 2));

    cout << "96명 중 두 사람이 동일한 생일을 가질 확률: " << p * 100 << "%" << endl;

    if (cnt == 0) {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << '0' << endl;
    }
    else {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << cnt << endl;
        cout << "동일한 생일을 가진 쌍의 날짜:" << endl;
        for (int i = 0; i < contain.size(); i++) {
            cout << contain[i] << endl;
        }

    }

    fp.close();

}

void quickSort(vector<int>& quick, int i, int j) // i: low, j: high
{
    if (i >= j) return;
    
    int pivot = quick[rand() % (i - j + 1) + i]; // -> pivot random하게 설정
    int left = i;
    int right = j;

    while (left <= right)
    {
        while (quick[left] < pivot) left++;
        while (quick[right] > pivot) right--;
        if (left <= right)
        {
            swap(quick[left], quick[right]);
            left++; right--;
        }
    }
    quickSort(quick, i, right);
    quickSort(quick, left, j);
}

 

4. Tuple sort

Time Complexity: nlogn

In-place: in-place

Stable: stable

1) The month comes first, and the date second

// tuple sort - 첫 번째 먼저 정렬, 그 다음 두 번째 정렬
#include <iostream>
#include <ctime>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;

bool compare1(const pair<int, int>& a, const pair <int, int>& b) {
    return a.first < b.first; // 첫 번째 수로 오름차순
}

bool compare2(const pair<int, int>& a, const pair <int, int>& b) {
    return a.second < b.second; // 두 번째 수로 오름차순
}

int main() {

    srand(time(NULL)); // 항상 random한 수가 나오도록 설정
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int cnt = 0;
    int n, birth1, birth2, find, min;
    double p;

    vector <int> contain;
    vector <pair <int, int>> v;

    ifstream fp("birthday_seperate.txt");

    if (fp.is_open()) {
        fp >> n;
        for (int i = 0; i < n; i++) {
            int birthday;
            fp >> birth1 >> birth2;
            v.push_back(make_pair(birth1, birth2));
        }
    }
    else {
        cout << "no file exist" << endl;
    }
    
    for (int j = 0; j < v.size(); j++) { // 첫 번째 먼저 오름차순 
        sort(v.begin(), v.end(), compare1);
    }
    
    for (int j = 0; j < v.size(); j++) { // 두 번째 오름차순 
        sort(v.begin(), v.end(), compare2);
    }
    
    for (int i = 1; i < v.size(); i++) {
        if (v[i - 1] == v[i]) {
            contain.push_back(v[i].first);
            cnt += 1;
        }

    }

    p = 1 - pow(double(364 / 365), (n * (n - 1) / 2));

    cout << "96명 중 두 사람이 동일한 생일을 가질 확률: " << p * 100 << "%" << endl;

    if (cnt == 0) {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << '0' << endl;
    }
    else {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << cnt << endl;
        cout << "동일한 생일을 가진 쌍의 날짜:" << endl;
        for (int i = 0; i < contain.size(); i++) {
            cout << contain[i] << endl;
        }

    }

    fp.close();

}

2) The date comes first, and the month second

// tuple sort - 두 번째 먼저 정렬, 그 다음 첫 번째 정렬
#include <iostream>
#include <ctime>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <fstream>
using namespace std;

bool compare1(const pair<int, int>& a, const pair <int, int>& b) {
    return a.first < b.first; // 첫 번째 수로 오름차순
}

bool compare2(const pair<int, int>& a, const pair <int, int>& b) {
    return a.second < b.second; // 두 번째 수로 오름차순
}

int main() {

    srand(time(NULL)); // 항상 random한 수가 나오도록 설정
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int cnt = 0;
    int n, birth1, birth2, find, min;
    double p;

    vector <int> contain;
    vector <pair <int, int>> v;

    ifstream fp("birthday_seperate.txt");

    if (fp.is_open()) {
        fp >> n;
        for (int i = 0; i < n; i++) {
            int birthday;
            fp >> birth1 >> birth2;
            v.push_back(make_pair(birth1, birth2));
        }
    }
    else {
        cout << "no file exist" << endl;
    }

    for (int j = 0; j < v.size(); j++) { // 두 번째 먼저 오름차순 
        sort(v.begin(), v.end(), compare2);
    }

    for (int j = 0; j < v.size(); j++) { // 첫 번째 오름차순 
        sort(v.begin(), v.end(), compare1);
    }

    for (int i = 1; i < v.size(); i++) {
        if (v[i - 1] == v[i]) {
            contain.push_back(v[i].first);
            cnt += 1;
        }

    }

    p = 1 - pow(double(364 / 365), (n * (n - 1) / 2));

    cout << "96명 중 두 사람이 동일한 생일을 가질 확률: " << p * 100 << "%" << endl;

    if (cnt == 0) {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << '0' << endl;
    }
    else {
        cout << "96명 중 동일한 생일을 가진 쌍의 개수: " << cnt << endl;
        cout << "동일한 생일을 가진 쌍의 날짜:" << endl;
        for (int i = 0; i < contain.size(); i++) {
            cout << contain[i] << endl;
        }

    }

    fp.close();

}

 

 

참고 자료)

Chatgpt

https://www.enjoyalgorithms.com/blog/introduction-to-hash-functions

Hash Functions in Data Structure

https://gazelle-and-cs.tistory.com/58

선형 시간에 중간값 구하기 (Quick-Select & Median-of-Medians)

https://st-lab.tistory.com/250

자바 [JAVA] - 퀵 정렬 (Quick Sort)