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

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

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 asymptotic notation.

Most algorithms end quickly if the input size is small, regardledd of the efficiency of the algorithm.

But, if the input size is large, will be a difference in speed. Therefore, when analyzing the execution time of the algorithm, always analyze the inpust size large enough. This is called asymprotic nanlysis.

Typically, there are five notations.

• Big O notatios.
• Small O notiations.
• Omega notiations.
• Little Omega notations,
• theta notation.

Let me write one by one.

Bit O notation

Big O notation is used computher enginerring to express the complexty or performance of an algorithm.

Big O notation represents the worst case.

O(1)

O(1) means that the execution time(or space) of the algorithm is always the same regardless of the size of the input data.

In this case, the if statement is executed on once regardless of the size of the input intarrays.

O(N)

O(N) means that the processing time increases proportionally to the amount of Input.

In this case. intarrays[i] and index value may be equal to each other in the middle.

Remember, Big O notations is represents performance for the worst case.

This is, the limits value that assumes that the maximum iteration

O(N²)

O(N²) represents a situation where performance is increased in proportion to the power of the power of the size of the input data

In this case, this is typically the case when nested loops are performed od data values thar are predominant.

O(log N)

O(log N) represent a case where the processing time increases slightly depending on the size of the input data.

A binary search algorithm is typical!!

Most algorithms have good algorithms.

O(2ⁿ)

O(2ⁿ) represents the case where the processing time increases by 2times every time the input data increases by one.

O(2ⁿ) is called worst algorithm.

The big O signs are summarized as follows.

O(1) < O(log N) < O(N) < O(N²) < O(2ⁿ)

Little o Notation

Little o notation is used to express  upper bounds that are more spacious than Big O notation.

Little o notation is not often used to indicate the complexity or performance of an algorithm.

If the analysis time of an algorithm is O(log N), this means that the time required for the algorithm increases slowly over log N for Input size N.

It was hard to understand....

Which means it does not increase like log N, but increases like log N. O(log N) and o(log N) can not be the same growth rate, are used when it is obvious that they increase more slowly than log N.

Big Omega(Ω) notation

Big Omega notation, like Big O notation, is used to denote algorithm complesity or performance.

However, if Bit O notation is the worst, Bit Omege notation represents the best case.

This is the minimum time it takes to execute the corresponding algorithm.

Little Omega(ω) notation

Little Omega notation is used to represent upper bounds that are more spacius than Big Omega notation.

Like the Little O notation. 

If the analysis time of an algorithm is ω (log N), this means that the time required for the algorithm to grow slowly over log N for input size N.

It was hard to understand, which means it does not increase like log N, but increases like log N. That is, Ω (log N) and ω (log N) can not be the same rate of increase, but they are used when it is obvious that they will grow more slowly than log N.

Theta(Θ) notation

Theta notation.. Big O notation is worst case, and Big Omega notation is best case. Then Theta notation is average case.

Think it is the intersection of Big O and Big Omega.

So, this algorithm is within the theta range no matter hou good or bad it is, It's mean.

I've written a bit about asymptotic notation.

I'm not sure about the other four notations except for Big O.

In the future, I will post each of these 5 pieces one by one.

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 I will post about inline, one of the reserved words in C++

This is one of the reserved words that comes out when you look at c++ books.

To put it plainly, inline functions are where the coded of the complied function is inserted directly into the program's code.

Shall see the code?

When you compile the code.

It will changed as above. How about this?

Let's check with assembly code to see more results.

First, if you look at the main function of assembly code that is not inline.

Will come out as above.

Inline apply assembly code.

Come out like this.

Look at line 13, can see the difference.

Let's change the function more easily.

Source code

Assembly code not use Inline.

Assembly code use Inline.

Look at code 14, can feel the difference.

No call on the assembly code.

And push is not being called either.

Looking at the process of calling a generic function, first the stack is push parameters, and the function is called.

Then there are push and pop stack for the return value in the function. After return, there is pop for stack cleanup.

Because these function calls access the stack, they can slow down, because accessed by memory.

When use inline, the first thing is speed and memory effect.

Disadvantage is that if use it repeatedly, the assembly code becomes longer.

If the function is called multiple times and written in assemblycode.. is not that a joke?

Conclusion.

Well, my conclusion from my brief knowledge.

Function that has a short syntax and fewer calls is use inline.

I would appreciate it if you point out in a comment field. please.

Thankyou.

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

Hello, i am GameDeveloperPlayground.

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

I would appreciate pointing out grammar or typos.

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

Original Links : http://silisian.tistory.com/30

Why we have to study C language?

First. Each university first teaches C language.

why?

C language is the basis for all programming languages.

So, why is C the basis of all programming languages?

Many other programming languages are written in C or C language models.

So, why are many other programming languages written in C or C language models?

Let's look at history.

History at C language.

The reason is, of course, C language was used by a many programmers.

The reason why C language is loved so much is C language has merits.

C language was defines the basic things.

Also, Additional extensions are possible if the definition does not deviate.

So, C language has a lot of similar versions, there are so many different languages that can be called C languages.

American National Standards Institue( ANSI ) define ANSI C.

C lanuage which was created in this way, grew like a living life.

Every time new programming techniques and theories arise put it in C language. 

If the disadvantage of C language is found, have modified the structure of the language. 

C language is so very powerful and very messy programming language. :<

Because C language has beening revised since the year 1971.

C language is intermediate language.

Machinge language in the programming language  that can be understood by the machine, which is a combination of numbers 0, 1.

Assembly is a language that make it a little bit meaningful by matching it an English word.

Here are the low-level languages.

So, high-level language is that makes the instruction more meaningful from apart low level language.

C language is clearly high level language.

Origin of language names

Origin of C language name.

Once upon a time there was language called 'B language'. The language created by the motif is 'C language'.

Origin of C++ language name.

Once upon a time C language plus 'Class' called 'C with class', which is too long to be called 'C++'.

Origin of C# language name.

Once upon a time there was a language called 'C++', plus add one more '++' 

C++

  ++

Like C#. :>

C language projections

The C language is not used more often.

The reason id that it takes too long to create programs.

It's good for hardware control, but performance is getting lower because it's not as productive.

Comprehensive summary

C is good.

C has strong performance.

Many programming languages are written in C or C in motif.

However, the dfficiency of work is low.(To type a lot of batter) But is fast!!

C is so long many Programs are written is C.

To study them.

C must be! :>

thank you.