Please enable JavaScript.
Coggle requires JavaScript to display documents.
CHAPTER 6: SORTING & SEARCHING, shahrul(slide 11) - Coggle Diagram
CHAPTER 6: SORTING & SEARCHING
PART 1 - SORTING
Slide 14 (Anding)
Quick Sort
The basic concept is to pick one of the elements in the array as a pivot value around which the other elements will be rearranged.
Everything less than the pivot is moved left of the pivot (into the left partition).
Similarly, everything greater than the pivot goes into the right partition. At this point each partition is recursively quick sorted.
Quick Sort
(Dominic) - Slide 15
The picture above is showing Quick Sort
Wardina(Slide 10)
BUBBLE SORT
works by repeatedly stepping through the list to be sorted,
comparing two items at a time and swapping them
if they are in the wrong order
The pass through the list is repeated until no swaps are needed (loop)
a comparison sort
Example 1
Abdullah (Slide 8)
MERGE SORT
Merge sort is a comparison-based sorting algorithm.
Conceptually, a merge sort works as follows:
If the list is of length 0 or 1, then it is already sorted.
Otherwise:
Divide the unsorted list into two sub lists of about half the size.
Sort each sub list recursively by re-applying merge sort.
Merge the two sub lists back into one sorted list.
(
Mauldorna, Slide 9
)
Example
a sorting technique based on divide and conquer technique.
it is one of the most respected algorithms.
slide 16 (Catherine)
Insertion Sort
Insertion sort is the sorting mechanism where the sorted array is built having one item at a time.
The array elements are compared with each other sequentially and then arranged simultaneously in some particular order.
Insertion slide 17 gibson
To sort an array of size n in ascending order, use the following syntax:
1: Iterate through the array from arr[1] to arr[n]. 2: Contrast the present element (key) with its predecessor.
3: If the key element is smaller than the one before it, compare it to the components preceding it. To make room for the switched element, move the larger elements one place higher.
slide 6 (Haziq)
Selection Sort
slide 7(Syazwan)
Example
no 2 exchange to the first place. no 10 to the fifth place
no 5 remain in the second plae
no 8 exchange place with no 100
1 more item...
Specifically an in-place comparison sort is the algorithm of selection sort.
With more complicated algorithms in certain situations, selection sort has shown its advantages for being simple to implement and has proved towards its performance.
athirah (slide 12)
BUBBLE SORT
list resulted from the second loop
Compare the second and third element to check which one is greater, and sort them in ascending order.
Compare the third and fourth element to check which one is greater, and sort them in ascending order.
Compare the fourth and fifth element to check which one is greater, and sort them in ascending order.
Wan(Slide 13)
BUBBLE SORT
List resulted from the the last loop.
All compare elements should be unchanged.
Elton(slide4)
DEFINITION
Sorting is any process of arranging items in some sequence and/or in different sets, and accordingly, it has two common, yet distinct meanings
Ordering: arranging items of the same kind, class, nature, etc. in some ordered sequence,
Categorizing: grouping and labelling items with similar properties together (by sorts)
VARIOUS TYPE OF SORTING*
SLIDE 5(ayuna)
1.Selection Sort
2.Merge Sort
3.Bubble Sort
4.Quick Sort
5.Insertion Sort
PART 2 - SEARCHING
LINEAR SEARCH
JAZRIN ( SLIDE 22)
This diagram is about searching 14 with linear search method.
Searching process will begin with the first index which is index 0 and it will compare the data in index 0 with the search key, whether the data in index 0 equal to search key and if the data in index 0 not equal to search key, it will go to next index and do the same process. This searching process will continue until it found the data equal to search key and search is successful.
BINARY SEARCH
Abdullah (slide 27)
(5 + 6)/ 2 = 5.5
M= 5
Key = 21
M = 21
21 = 21
Searching stop and successful
Syazwan(slide 26)
Key = 21
21<36
21 ! = 36
M = 36
Elton(slide24)
Let say, we want to search whether 21 is in the list .4,7,8,10,14,21,22,36,62,77
First determine the middle(pivot) of the list using this formula:
middle = (lowest index) + ( highest index) /2
(0 + 9)/ 2 = 4.5
M= 4
Haziq (Slide 25)
Key = 21
M=14
21!=14
21>14
To start, find the middle point of the table (by index number F+L/2, round down), confirm that it is not 21. Since 14 is lower than 21 then any number before it and itself is irrelevant. Therefore, it gets canceled out.
erika (slide 20)
SEARCHING DEFINITION
the process used to find the location of a target among a list of objects.
in data processing context is a process to find the location of data in a list or table given. It’s being done by comparing each data item with the search key.
ARIF (SLIDE 21)
LINEAR SEARCH
The linear Search is can be used whenever the list is in order or not ordered.
Generally, linear search are used only for small lists or lists that are not searched often.
In linear search, we start searching for the target at the beginning of the list and continue until we find the target or we are sure that it is not in the list.
This approach gives us two possibilities: either we find it or we reach the end of the list.
LINEAR SEARCH EXAMPLE
(SLIDE 23)-ayuna
shahrul(slide 11)
