'Quick'에 해당되는 글 1건

  1. 2016.12.09 [Algorithm] About Quick Sort.
2016. 12. 9. 14:03

[Algorithm] About Quick Sort.

Programing/Algorithm

Hello, i am GameDeveloperPlayground.

I am a Korean student and I post it for English practise.

I would appreciate pointing out grammar or typos.


In this posting in about select sort.



About Quick Sort


Quick sort algorithm is developed by Charles Anthony Richard Hore(1962).


Quick sort is selects the pivot to place data smaller than the pivot to the left, and large data to the right.

At the end of this process, the pivoted element finds the aligned position. As a result data smaller than the standard is left, and large data to the right.

In this algorithms are repeated until the left data group and the right data group are no longer resursively based on pibot(Repeat until the number of data groups count is 0 or 1)

At the end of ther repeat, can get a sort groupd of data.



(출처 : 위키백과 퀵정렬)




Sorting process



Le't sort by random data array

15 13 9 10 26 24 85


1. Set up Pivot



15 13 9 10 26 24 85


2 IF is smaller than the pivot, it is dicided info left and right sides.

13 9 03 15 26 24 85


3. Repeat algorithms with left and right data.


( 13 9 10 )   15   ( 26 24 85 )

( 13 9 10 )   15   ( 26 24 85 )

( 9 10 13 )   15   ( 26 24 85 )

( 9 10 )   13 15   ( 26 24 85 )


9 10 13 15   ( 26 24 85 )

9 10 13 15   ( 26 24 85 )
9 10 13 15   ( 24 26 85 )


9 10 13 15 24 26 85


Completed!


Example Code


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
void QuickSort(int arrays[], int left, int right)
{
    if(left<right)
    {
        int pivot = Partition(arrays,left,right);
        QuickSort(arrays, left, pivot-1);
        QuickSort(arrays, pivot+1, right);
    }
}
 
int Partition(int arrays[],int left, int right)
{
    int pivot = left;
    right = right +1;
 
    while(left<right)
    {
        do
        {
            ++left;
        }while(arrays[left] < arrays[pivot]);
 
        do
        {
            --right;
        }while(arrays[right] > arrays[pivot]);
 
        if(left<right)
        {
            int swap = arrays[left];
            arrays[left] = arrays[right];
            arrays[right] = swap;
        }
    }
 
    int swap = arrays[pivot];
    arrays[pivot] = arrays[right];
    arrays[right] = swap;
 
    return right;
}
cs


another code


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
void QuickSort(int arrays[], int left, int right)
{
    int row = left;
    int high = right;
    int pivot = arrays[(left + right) / 2];
 
    while (row <= high) {
        while (arrays[row] < pivot)
            row++;
        while (arrays[high] > pivot)
            high--;
 
        if (row <= high) {
            int tmp = arrays[row];
            arrays[row] = arrays[high];
            arrays[high] = tmp;
            row++;
            high--;
        }
    };
 
    if (left < high)
        QuickSort(arrays, left, high);
 
    if (row < right)
        QuickSort(arrays, row, right);
}
cs




Algorithm analysis



The time complexity in the most average situation is the time complexity of the algorithm.


There are two main situations.


1. In the best case, it is divided by half for every family member.

2. In the worst case, when divided into one and the rest per family.


First, we calculate the case of 1.


Number of times = (2ⁿ - 1) + 2x (2ⁿ -¹¹) ...

= ⁿ-¹Σ 2 ... I do not know how to write this formula.


Calculate ... NLogN comes out.


In case of 2, it is N².


Later, if you know how to add formulas properly ... then I'll have to fix them.



In any case, since the second case is an extreme situation, the time complexity is O (N logN) using the first case.


Thank you.









저작자표시 비영리 변경금지

'Programing > Algorithm' 카테고리의 다른 글

[Algorithm] About Select Sort  (0) 2016.12.08
[Algorithm] About Insertion Sort  (0) 2016.12.08
[Algorithm] About Bubble Sort !!  (0) 2016.12.08
[Algorithm] About Linear Search  (0) 2016.12.08
[Algorithm] About Binary Search Algorithm.  (0) 2016.12.08
Posted by 시리시안

티스토리툴바