DSA - Sorting Flashcards
Describe Sorting:
- Given a set of records, we can sort them many different
Criteria. - Normally Sorting, not just key values
- Sort algorithm mostly work on the basis of a comparisons
Order in which you can sort:- Decreasing Order
- Alphabetic Order
- Increasing Order
What are the 2 Interfaces to implement Comparison functions?
- Comparable
- Comparator
Explain how Comparable works?
- Object can compare itself with another object using the
compareTo(…) method - Can only have 1 compareTo method at a time
- x.compareTo(y)
- should return 0 if x is equal to y
- should return anything < 0 if less than
- should return anything > 0 if greater than
Explain how Comparator works?
- Object can compare 2 objects of the same type using the
compare(…) method - Can have multiple compare, thus can have multiple orders.
- compare(x,y)
- should return 0 if x is equal to y
- should return anything < 0 if less than
- should return anything > 0 if greater than
Define Enumeration :
- Each item, count the number of items less than it.
- For every item count the number that is less than it and then
knowing that put the value in correct order in list of al items
(GIVES INDEX)
Define Exchange:
- If 2 items are found to be out of order we exchange/SWAP
them. - e.g. Finding 2 items then swapping them, repeat this for all
items that are not in order.
(CONTINUES TILL ITEMS ARE IN ORDER)
Define Selection:
- Find the smallest item, put it in position 1, then find the next
smallest and put in the next index. - Each time selecting smallest item and putting it into correct
position.
Define Insertion:
- Take items one at a time and insert into an initially empty data
structure such that the data structure continues to be sorted
at each stage. - Place the item in a specific position in an already sorted array
just reassign it to correct index
Define Divide & Conquer:
- Recursively splits the problem into smaller sub problems till
you have a single items that are trivial to sort. Then sort the
parts back together preserving the sort/
Define Stable Sort :
Does not change the order of items in the input if they have the same sort key
Explain Bubble Sort:
Multiple passes over an array of items, swapping neighbouring items.
=> Only swaps neighbouring items that are out of place
=> First pass definitely get items in index 0, Second pass
second smallest items in index and so on
=> May get more than one value in the correct order
What is Complexity of Bubble Sort?
Outer Loop = n-1 times
Inner Loop = n-i times
thus total comparisons are : (n(n-2))/2 == (n-1)+(n-2)+…+(1)
==> (n^2-n)/2
// Each iteration executes a single comparison. Measuring complexity by counting No. of comparisons.
Is Bubble Sort Stable?
Yes, because bubble sort can only swap values strictly smaller than itself and will not swap values equivalent (THE SAME), thus does not change and they retain their order of elements.
NEVER SWAPS 2 RECORDS AROUND IF THEY HAVE SAME KEY VALUE
CODE for Bubble:
bubblesort(a,n){
for(i = 1 ; i<n; i++){
for(j = n-1; j>=i ; j–) { // Starts on last element and works
if(a[j] < a[j-1]) { // down
swap a[j] and a[j-1]
}
}
}
} // Basic version of Bubble Sort has no Optimisation
Define Insertion Sort:
Taking each element of the input and inserting it into its correct position relative to all the elements that have been inserted so far
- Sorted part is usually the first element in the array and the rest is unsorted
- Takes the first element of the unsorted part & inserts it into its correct position in the sorted part,
(Growing sorted part & shrinking the unsorted by one cell)
Complexity of Insertion Sort?
- Outer Loops Iterates n-1 times
- Worst case:
-Inner Loop iterates once for first outer loop and twice
for the 2nd outer iteration etc.
-Worst case is 1+2+…+(n-1) == (n(n-1))/2- Sorting Array in reverse order have to go all the way to
end of the sorted Array. (MAX Amount of Shifting)
- Sorting Array in reverse order have to go all the way to
- Average case:
- Half the Worst time - due to on average the correct
position for the insertion in each inner loop will be in
the middle of the sorted part
- (1+2+…+(n-1))/2 == (n(n-1))/4 - Hence AVG & WORST case is O(n^2)
Is insertion Sort Stable?
IS STABLE, BECAUSE:
- 1st Occurrence of 2 copies of the same value will be taken
before 2nd.
- Must Be strictly greater than to cause a swap
- We will not insert later copy of a value before an earlier
copy that has already been inserted
Define Selection Sort:
Works by Selecting the smallest remaining element of the input array and appending it at the end of all the elements that have been inserted so far.
SPLITS ARRAY INTO 2 PARTS SORTED & UNSORTED
Describe Selection Sort:
First Pass: smallest item from unsorted part and swap with first element and then next smallest swap with the second element repeat till last smallest element is found
Look through unsorted part of the Array & find what’s the next VAL we have to put in
Selection Sort Code
selectionSort(a (list) , n (size)){
for(i =0 ; i < n-1 ; i++){
k = i
for(j= i+1 ; j<n ; j++){ // Linear search to find
if(a[j]<a[k]){ // Smallest value. if smaller
k = j // swap & index j is smallest
}
}
swap a[i] and a[k] // swaps elements
around
}
}
Selection Sort Complexity:
- Outer Loop is iterated n-1 times
- Worst Case:
- Inner Loop is iterated n-1 first time and n-2
for second outer iteration - This is Best/Worst/Average Case
- Total No. of Comparisons:
(n-1)+…+2+1= (n(n-1))/2 - Overall worst/ AVG case Complexity = O(n^2)
Selection Sort Stability:
Shuffling unsorted parts of the Array. Therefore, thus changes the position of element. Thus, Changing order, so NOT STABLE.
e.g:
list: 2_1,2_2,1
swaps 2_1 with 1 thus swapping index 0 and 2
list: 1,2_2,2_1
No more swaps, But the order of 2s don’t change
Describe Heap Sort:
- Insert elements into a priority queue
- Take out highest priority & put at end of array
- Each time you Remove highest priority element, it
will decrease the number of elements u r using
for BHT - Take OUT next priority and place into spare space
Define Heap Sort:
Uses a priority heap to sort all the values by constructing a priority heap with the unsorted values and repeatedly removes the largest value and puts it into OUTPUT array starting at the end & working backwards towards the start of the array.
What is Good about Heap Sort?
Without doing a lot of copying & allocating, end up sorting queue
But in locations 1 => n
Heap Sort CODE:
heapSort( array a , int n){
heapify(a,n) // Heapify the ARRAY
for (j= n ; j > 1 ; j–){
swap a[1] and a[j] (2)
bubbleDown(1,a,j-1)
// ON smaller array that is result of removing 1
element from it
}
}
//The Swap (2) => the highest priority moves to end of ARRAY & Last value moves to root or index of highest priority
Heapify Complexity?
O(n)
BubbleDown Complexity?
O(log n)
Total Complexity of Heap Sort?
O(n log(n))
==> Have to do n bubble downs, which is O(log n)
so it is n * log n = O(n log(n))
