::GameDeveloperPlayground::

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 )

another code

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.

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 Select Sort

Select sort is sorted is three ways.

1. Find the minimum value in a give array.

2. Replace the value with the value at the front of the array.

3. Replace the array with the first position subtracted in the same way.

Sorting Process

Let's start by randomly array numbers.

9 5 4 3 8 1 7

First find the lowest value in the unaligned array { 9 5 4 3 8 1 7}

It's 1. Replace the found value with the first value.

9 5 4 3 8 1 7 => 1 5 4 3 8 9 7

this one loop is over.

The second is to sort the array except for the first value, 

Find the lowest value 1 { 5 4 3 8 9 7 }. It's 3. Replace with the first array except 1

1 3 4 5 8 9 7

This is the way to go to the end.

(출처 : 위키백과 선택정렬)

Sample Code.

Implemented simply.

Algorithms analysis

Select sort is should be done entirely to get he minimum value. Therefore.

(n-1) + (n-2) + ..... + 2 + 1 = n(n-1)/2 

The time Complexity will be O(N²) with Big O notation.

Example.

(source:  위키백과 선택정렬 )

Video Example

( source: Youyube )

Thank you

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 Inserting Sort.

About Insertion Sort

Insertion sort is an algorithm that compares all the element of data array with parts of array that have already been sorted from the first to the last.

In the case of Insertion Sort, the first element is already aligned. And start sorting.

Unsorted elements ar insered at the appropriate position relative to the sorted list starting with the last element in the list.

Repeat this operation until all elements ar sorted.

Sorting process

Show you a simple insertion sort example.

5 numbers are given as below, will sort by insertion sort.

4 9 2 5 7

Insertion sort determines that the first element is aligned and starts from the second.

First

4 / □ 2 5 7  | key value = 9

9 is greater than 4 and is located behind 4. 4 □ 2 5 7 

4 / 9 2 5 7 

Second

4 9 / □ 5 7 | key value = 2

2 is less than 9, so it is located in front of 9. 4 □ 9 5 7 

2 is less than 4, so it is located in front of 4. □ 4 9 5 7

2 4 / 9 5 7

Third

2 4 9 / □ 7 | key value = 5

5 is less than 9, so it is located in front of 9. 2 4 □ 9 7

5 is greader than 4, so it is located behind 4. 2 4 □ 9 7

2 4 5 / 9 7

fourth

2 4 5 9 / □ | key value = 7

7 is less than 9, so it is located in front of 9. 2 4 5 □ 9

7 is greater than 5, so it is located behind 5. 2 4 5 □ 9

2 4 5 7 9

Sorting is complete.

(Source : 나무위키 삽입정렬)

Example Code

It is Simple.

Algorithm analysis

Number of comparisons.

Insertion Sort is from the second element to the first element, than the third element is compared to the second and first.

Of course, if it's already sorted, will not compare.But it is worst case.

0 + 1 + 2 + 3 .... + n-2 + n-1 = n(n-1)/2

So in the worst case, the time complexity is O(N²).

In the best case, the comparison is O(N).

Below is the data I found when I searched for Insertion sort.

Insertion Sort Image Example.

( Source : 위키 백과 : 삽입 정렬 )

Example video of Insertion Sort.

Source ( 유투브 동영상(클릭) )

Thank you