Yo-yo Sort & Deduping Sticker

- 요요 정렬 ( Yo-yo Sort )

시간복잡도 O( n + k ) / 공간복잡도 O( n + k )

n : 배열의 길이
시간복잡도 k : Max - Min + 1
공간복잡도 k : 중복의 개수

원리

1. Hash Table에 값, 개수를 각각 Key, Value로 할당함
2. 기본 배열 값 삭제
3. 최소 ~ 최댓값을 반복하며 Hash Table에 저장된 것 차례로 배치
자세한 내용은 pdf를 확인해주세요.

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def YoyoSort(List):
    Min = min(List)
    Max = max(List)
    Dict = {}
    for x in List:
        if Dict.get(x) == None:
            Dict[x] = 1
        else:
            Dict[x] += 1
    
    New = []
    for x in range(Min, Max+1):
        if Dict.get(x) != None:
            New.extend([ x for _ in range(Dict[x]) ])
    return New
Colored by Color Scripter
cs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
private static void YoyoSort(int[] OriginalArray, int Length)
{
    int Min = int.MaxValue;
    for (int i = 0; i < Length; i++)
    {
        if (OriginalArray[i] < Min)
        {
            Min = OriginalArray[i];
        }
    }
 
    int Max = 0;
    for (int i = 0; i < Length; i++)
    {
        if (OriginalArray[i] > Max)
        {
            Max = OriginalArray[i];
        }
    }
 
    Dictionary<int, int> CountDict = new Dictionary<int, int>();
 
    for (int i = 0; i < Length; i++)
    {
        if (CountDict.ContainsKey(OriginalArray[i]) == false)
        {
            CountDict.Add(OriginalArray[i], 1);
        }
        else
        {
            CountDict[OriginalArray[i]]++;
        }
    }
 
    int Index = 0;
    for(int i = Min; i < Max + 1; i++)
    {
        if (CountDict.ContainsKey(i) == true)
        {
            for(int x = 0; x < CountDict[i]; x++)
            {
                OriginalArray[Index] = i;
                Index++;
            }
        }
    }
}
Colored by Color Scripter
cs

- 중복제거 스티커 ( Deduping Sticker )

시간복잡도 O( n + x ) / 공간복잡도 O( n + k + j )

n : 배열의 길이
x : 사용될 정렬의 시간복잡도 / Quick Sort 의 경우 x = n log n
k : 중복의 개수
j : 중복이 제거된 배열의 길이

원리

1. Hash Table에 값, 개수를 각각 Key, Value로 할당함
2. 배열 정렬
3. Hash Table 내 값과 개수를 토대로 배열 할당
자세한 내용은 pdf를 확인해주세요.