::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

----------------------------------------------------------------------

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 bubble sort.

Bubble Sort 

Bubble Sort is a simple sorting algorithm that compares two adjacent numbers and sends them back a large number.

Time complexity is O(N²). The speed is slow, but the code is simple.

Said that the movement of the element is called bubble sort because the bubble appears to be rising to the suface of the water.

Sorting process

Show an example of simple bubble sorting.

Let's say have 5 numbers given below. Sort by Bubble Sort.

9 5 1 3 7

First, compare the first index with the second index.

9, 5 . 9 is larger change the place of two numbers.

Before the change : 9 5 1 3 7

After change : 5 9 1 3 7

Increase the next index by one and compare the second and third indexes.

9 is larger, thery change the place of two numbers.

Before the change : 5 9 1 3 7

After change : 5 1 9 3 7

Continue to increase the Index, complare the values, and change the position.

Before the change : 5 1 9 3 7

After change : 5 1 3 9 7

Before the change : 5 1 3 9 7

After change : 5 1 3 7 9

Onetime tour is over. As the tour of the circle was over, the biggest number 9 went to the spot.

So in the next tour, you do not need to visit the last element.

Fix the last element 9, Let's proceed with the remaining elements.

Before the change : 5 1 3 8 9

After change : 1 5 3 7 9

Before the change : 1 5 3 7 9

After change : 1 3 5 7 9

Before the change : 1 3 5 7 9

After change : 1 3 5 7 9

The Second tour is over. As an example, a few random numbers are completedd in just two iterations

This is Bubble Sort!! HaHA

Example Code

It's a simple.

Algorithm analysis

Sorting algorithms need to be analyzed.

I Wrote down the time complextiy as O (N²), but need to know how to get it.

Number of comparisons

Bubble Sort is reduced by one each time you complete a tour.

Total number of elements is n, the sorting is completed when the total n-1.

If sort the five element arrays, you will compare 4+3+2+1 = 10 times.

Formulate this.

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

Number of Exchanges

In the best case, not be a swap during the sorting process.

In the worst case, since every time compare elements, the number of excahnges will be equal to the number of comparisons.

Best Case Replacement count : 0

Tho Worst case number of Exchanges :  : n(n-1)/2

Adding the number of comparisions and The number of exchanges gives n²-n.

There fore time complexity is O(N²) in BiG O notation.

Below is the data i found when I searched for bubble sorting data.

Example video of Bubble Sort

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

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 about Linear search.

Linear Search

An alogirthm that searches sequentially from top to bottom.

Time complexity has O(n)

Terminiation condition

If the array find a number in arrays. or if it can not be found until the end, it will be terminiated.

Example Code

It's simple.

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 post, about Binary search Algorithm.

Binary Search

Data sorting is required to run the binary search algorithm.

Let's look at how algorithm work.

find for number 5 in the array { 1, 3, 4, 5, 7, 8, 10, 20, 60, 100 }.

First case

Divide array start index and last index value by two.

Check whether the value corresponding to the index is 5 or not if it is 5 or smaller.

( 0 [start index] + 9 [last index] ) /2 = 4.5 (discard the rest) => 4

Since array[4] is = 7. the values not equal.

Array[4] is greater than the value 5. 4~exclude form the dearch until in the list index.

Second case

(0 [Start index]) + 3 (List index) / 2 = 1.5 => 1

array[1] is 3 , not equal.

array[1] is smaller than 5. it excludes from startindex ~ 1.

Third case

(2 [start index]) + 3 [last index] ) /2 = 2.5 => 2

array[2] is 4, not equal.

array[2] is smaller than 5, it excludes from startindex ~2.

Fourth case

(3 [start index])  + 3 [last index]) /2 = 3

array[3] is 5. return the same value index. and end the search.

The time complexity is O(Log N) because retrieve the value by decreasing by half as above.

If the value is not found, return failure value.

Example code

The terminiation condition of the algorithm.

If the start index(from) is greater than the lst index (to) as in the above code, it terminates.

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 post, about Fibonacci sequence.

Fibonacci sequence

Fibonacci sequence is that adds the previous two numbers to create the number of current positions.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...

Except for the start two numbers 0 and 1, summarize the total number of previous number and previous number at previous number atfer the third.

0, 1, (0+1) , ((0+1) + 1) , (((0+1) + 1) +(0+1)) ...

There are a number of ways to implement such a simple algorithm.

Fibonacci sequence implementation using recursive function call.

The first and second values are set to 0 and 1, respectively returning 0 and 1, and returning the sum of the previous of n and the previous of the previous of n.

have just completed implementation, but every time enter the Algorithm function need to check wgether n is 1 or 2.

have implemented it as a loop this time to remove the fuplicate test twice.

Changed the part that calls tell recursive function to thefor statement.

Current is the current number, and befroevalue is the previous number.

The next number is the current number plus the previous number. so you can add current and before value.

Other ways to do it...  Similar in performance, but there is another ' tail recursion' implementation. in code.

After one hour

Before is next

Next is before + next.

So iterates through the tail recursion function and returns the current value (before) if the value of n is zero.

We will discuss the tail recursive function in detail in another post.

Thank you.