Introduction

• The selection sort is very similar to that of bubble sort. Instead of finding a max however, It repeatedly finds the minimum element from the unsorted portion, and puts it into a “sorted portion”

Why is it Important?

• Selection sort is the next logical step from bubble sort. It does what bubble sort does, but has one large difference. Instead of searching through the entire array each time, it creates and only searches an “unsorted portion”.

Lesson Notes

• The algorithm works by creating two subarrays within an array. The first subarray is the portion that is already sorted. The second is everything that is unsorted. Typically this is kept track of with an index number. So if our index number was 3, then everything to the right of and equal to 3, is the current sorted portion.

• As you can see in the figure above, with each operation, the sorted portion grows and the unsorted portion shrinks. The algorithm works by finding the minimum number, then swapping it with the array index closest to the sorted portion.

• For example, in the first example, 8 is the number that will be swapped. This is because the sorted portion doesn’t exist yet, so the 8 is the closest to the left. We then go through the array and find the minimum value, which in this case is 1. We swap 8 and 1 and do it again.

• The 1 is now in the sorted portion. We move to the closest value to the sorted portion (So one to the right of the boundry of the sorted portion) which is the 5. We then look for the smallest number in the unsorted portion. We find the 3, and swap the 5 and 3. Now the sorted portion is two big. We continue this process until the entire array is sorted

• This although slightly faster than bubble sort, doesn’t improve the run time by any large magnitude. It still is on average a runtime of n^2. You can see the math for this under the diagram. It is still making n(n-1)/2 comparisons. This reduces to (n^2-n)/2 operations. Remember when we go to infinity we grab the largest magnitude. So in this case, the n^2 is the only thing that stays.

• Best Time: Ω(n^2) : Even if the array is already sorted, selection sort must run through its entire algorithm to figure this out. This means it will generate an already sorted portion, and only increase it by 1 on each operation. So the total run time will still come out to be n^2

• Average Time: Θ(n^2) : Same with the average time. It doesn’t matter how unsorted or sorted the array is, it will run through all operations each time. Although the magnitudes of this and bubble sort are the same, this one is technically faster because it reduces the size of the search area each time, unlike bubble sort which searches the entire array each time.

• Worst Time: O(n^2) : Same with the worst-case time. It will use the same operations no matter how sorted or unsorted the array is. No one case is better or worse for selection sort.

Quiz

논문을 Accepted를 받거나 논문 쓴것을 교수님 등에게 confirm을 받게 될 때 가끔 pdf 파일로 변환되면서 화질이 깨지는 문제에 대해 스트레스를 받은 적이 많다.

인터넷을 통해 컨버트를 해보고, 구글링을 하면서 문제를 해결하는데 있어 속시원하게 해결된적이 없었다.

여러 테스트를 하는 도중 100% 워드파일의 이미지가 깨지지 않고 pdf로 전환되는 방법을 찾게 되었다.

Introduction

• Bubble Sort is arguably the simplest sorting algorithm. It works by repeatedly swapping adjacent elements that are in the wrong order.

Why is it Important?

• A study of sorting algorithms always starts here. This is because the intuition behind Bubble Sort is really easy to understand, and it’s good to analyze why this algorithm is not efficient. We can then use that to move in to the more advanced sorting algorithms.

Lesson Notes

• The algorithm works by “bubbling up” the largest value each time. It does this through simple swaps of data in the array.

• This creates a “First In First Out” relationship with the data. Where in a stack there is a chance the first element could never get touched, in a queue it is a lot more “fair”. The most recent to come in will not be removed until every piece of data that was there before it is removed.

• The naming convention for removing and adding to a queue are typically dequeue and enqueue, respectively. However, it isn’t uncommon to see pop and push used for a queue as well.

• As you can see in the figure above, in each pass through the algorithm it starts at the left side of the array. It grabs the first number and sets it as the maximum. If the next number in the array is smaller than this number, it swaps their position. If the next number is larger, it sets the max to this number, and continues down the array.

• Items are only swapped with adjacent numbers. So each pass will successfully “bubble” the next largest number up to the top of the array.

• For example, above in step 1, it starts at the -2 and set’s that to max. It then looks at the 45. Well the 45 is larger than -2, so it makes 45 the new max. It then looks to the right of 45 to the 0. It sees that the 0 is less than 45, so it swaps the two. It does the same with the 11 and the -9. It is now the farthest to the right that it can go, so it stops and starts over again.

• This program however is not very efficient. On average it will run at O(n^2) time. This is because if the array is completely unsorted, or sorted backwards, there is a good chance it will have to run through the entire array, which has n amount of elements, n amount of times. (Since only one element is sorted at a time. It has to keep running through the array over and over again)

• Best Time: Ω(n) : This happens if the array is already sorted. It only has to run through the array one time. However, this is a sorting algorithm, so the chance the data is coming in sorted is very slim.

• Average Time: Θ(n^2) : This happens because of the fact that it will most likely have to run through the array n times. Since the array is length n, this means that it will be nXn or n^2

• Worst Time: O(n^2) : This happens because of the fact that it in it’s worst case, it will have to run through the n array n amount of times. Since the array is length n, this means that it will be nXn or n^2. The worst case scenario for bubble sort is if the array comes in in reverse sorted order.

STL

• STL(or Standard Template Library) is a set of templates used to make the code
• SIMPLE and EASY TO write
• how do we use STL?
  • just write #include <bits/stdc++.h>

EXAMPLE (Max, swap)

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int a = 5, b = 8, maximum;

    // Maximum from a and b;
    maximum = max(a,b);

    // swapping two value
    swap(a,b); // a= 8, b = 5

    return 0;
}

EXAMPLE(double pow)

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int a = 5, b = 8, maximum;

    // Maximum from a and b;
    maximum = max(a,b);

    // swapping two value
    swap(a,b); // a= 8, b = 5

    // double pow (double base, double exponent);

    int number = 2;
    double cubicRoot;

    cubicRoot = pow((double)(number), 1.0/3); // 1(or 3) is of type int / 1.0(or 3.0) is of type double

    cout<<fixed<<setprecision(10)<<cubicRoot<<"\n"; // setprecision is 소수점 반올림
    cout<<fixed<<setprecision(3)<<cubicRoot<<"\n";

    return 0;
}

Introduction

• A queue is similar to a stack, but with one large difference, insertions and deletions take part from separate ends.

Why is it Important?

• Queues, just like stacks, are used for a variety of different tasks throughout computer science. They are great for processing data where order is important, like CPU operations, or tree traversals.

Lesson Notes

• A queue and a stack are very similar, except that a queue inserts and deletes from separate sides. This creates a data structure that is a lot like a line/queue to buy tickets for a concert. Everyone lines up near the box office. The first one that arrives is the first one that is served. The last one to arrive is the last one that gets served.

• This creates a “First In First Out” relationship with the data. Where in a stack there is a chance the first element could never get touched, in a queue it is a lot more “fair”. The most recent to come in will not be removed until every piece of data that was there before it is removed.

• The naming convention for removing and adding to a queue are typically dequeue and enqueue, respectively. However, it isn’t uncommon to see pop and push used for a queue as well.

Stack and Queue Run Benefits?

• Why use a stack or queue, what makes them special? In computer science, modeling is very important. Through modeling and abstraction we can take a machine that only does 1’s and 0’s and turn it in to anything we want.

• Stacks and queues are just another example of this abstraction. It’s just another layer of rules to add onto a pre-existing structure, so that we can control the data in a slightly different manner.

• Stacks are widely used in almost every aspect of computer design. Just through reading your email, hundreds of stacks are probably being implemented. Same with queues. Processors love queues as they give it a linear set of instructions to execute.

Stack and Queue Run Times

• Now, let’s take a look at some run times associated with these data structures.

• Because these data structures are so specialized, we can actually get O(1) run time on all operations of both stacks and queues. This is because we are only accessing the “ends” of the data structures. So we don’t have to worry about trying to get to the middle.

• Linked lists are usually best for these structures, as they can expand indefinitely

• With a stack, we just keep inserting and removing from the front of the data structure. We learned in the previous lessons that both of these operations are O(1).

• With a queue, we insert to the front and remove from the back. We can do this in O(1) time as well. (We would need to implement a tail pointer for this to work. It’s simply a piece of data that always points to the end of the linked list).

Example

Quiz