Introduction to Algorithms No.4

Hello. I have learnt and written the selection sort:

https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/selection_sort.c


I have also learnt the running time of an algorithm. The running time means how long it takes to execute an algorithm.
It is clear that it depends on the size of an input. It also depends on the input itself. Let's take an example of the insertion-sort algorithm. If the input array is already sorted, the running time is clearly shorter than the average running time. On the other hand, the input is reversely sorted, the running time is much longer.
And it is more important to think about the running time in the worst case. Because ...
I have to go to bed :(

See you tomorrow.

Comments

  1. KeroAug 12, 2018, 1:05:00 AM

    This comment has been removed by a blog administrator.

    ReplyDelete
    Replies
    1. UnknownAug 13, 2018, 6:42:00 PM

      An interesting point of view!

      They return the same value. But they are different functions. Considering what the input is, choose the best algorithm. For example, insertion sort runs much faster than the other sorting algorithms for an almost-sorted array. See wikipedia for details.

      Delete
    2. UnknownAug 13, 2018, 6:48:00 PM

      I am so sorry.........
      I have deleted your comment by mistake.......

      You said "Are the two algorithms(insertion sort and selection sort) implementing the same function but the different algorithm?"

      Delete
    3. KeroAug 13, 2018, 11:38:00 PM

      I see. I will try to write two algorithms tomorrow at my computer. Thanks for you answer.

      Delete

Post a Comment

Popular posts from this blog

Introduction to Algorithms No.3

Hello. I would have completed Chapter 2. But I have not. It takes a lot of time to think about and write algorithms. These are what I have finished writing today: https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/searching_problem.c https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/add_two_n-bit_integers.c The first program is about a searching problem. It receives an array and a number that the array has, as an input. Like (5, 3, 4, 2, 1), 4. Then it returns where the number is, as an output, 3. The second program is about adding two n-bit integers. It receives two n-bit integers as an input. Like (11010), (11100). Then it returns the sum of those integers as an output. Like (110110). In addition, I have learnt "loop invariant." I would like to tell you here. But it is difficult to explain. I will show you it some other time :( Thank you.
Read more

Introduction to Algorithms No.7

Hello. Today, I have started Chapter 4, "Divide and Conquer." And I have learnt "The maximum-subarray problem." Maximum-subarray algorithm can solve that problem. Suppose you have time series of stock prices, such as (5 10 4 2 3 7 1 5 6 2). You are at time 1 now. The stock price is 5 now. You know the future stock price (5 10 4 2 3 8 1 3 6 2). Then when will you buy the stock and sell it? The answer is, you should buy it at time 4 and sell it at time 6. Then you get 6. I have written two codes, which run with different running time. One algorithm runs with Theta(n^2). The other runs with Theta(n*log(n)). Therefore, the latter runs faster. The two algorithms are as follows: https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/maximum-subarray_problem_slow.c https://github.com/uriha421/introduction_to_algorithms/blob/master/I_Foundations/maximum-subarray_problem_fast.c You will be surprised to recognize that the slow program is mu
Read more

Introduction to Algorithms No.10

Hello. I have learnt introduction in "II Sorting and Order Statistics." Sorting algorithms and order statistics really matters in computer engineering, which encourages me to learn algorithms. The sorting algorithms have heap-sort, quick-sort, counting-sort, radix-sort, and bucket-sort. The order statistics means searching the n-th smallest number in a array. Tomorrow, I will tell you heap-sort. Thank you.
Read more