CS YEAR ONE > DSA - Sorting > Flashcards

DSA - Sorting Flashcards

(77 cards)

Study These Flashcards
1
Q

Describe Sorting:

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the 2 Interfaces to implement Comparison functions?

A
  • Comparable
  • Comparator
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Explain how Comparable works?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Explain how Comparator works?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Define Enumeration :

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Define Exchange:

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Define Selection:

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Define Insertion:

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Define Divide & Conquer:

A
  • 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/
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Define Stable Sort :

A

Does not change the order of items in the input if they have the same sort key

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Explain Bubble Sort:

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is Complexity of Bubble Sort?

A

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.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Is Bubble Sort Stable?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

CODE for Bubble:

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Define Insertion Sort:

A

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)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Complexity of Insertion Sort?

A
  • 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)
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Is insertion Sort Stable?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Define Selection Sort:

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

Describe Selection Sort:

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

Selection Sort Code

A

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
}
}

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

Selection Sort Complexity:

A
  • 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)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

Selection Sort Stability:

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

Describe Heap Sort:

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
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.
26
What is Good about Heap Sort?
Without doing a lot of copying & allocating, end up sorting queue But in locations 1 => n
27
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
28
Heapify Complexity?
O(n)
29
BubbleDown Complexity?
O(log n)
30
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))
31
Is Heap Sort Stable?
No due to the bubbleDown reordering nodes
32
Idea of Merge Sort?
1) Recursively, split the array in half until each element is in a single array 2) Once you cannot split the values any further, merge them and compare the values if smaller put it in front of the other value 3) Merge the 2 Arrays on the LHS/RHS, Compare values, smallest value goes in first, iterate once through of the smallest value. REPEAT for the other smaller values, then once you reach the end of 1 array add the rest of the values from the other array 4) Then Merge RHS to LHS, Compare the values in both list elements with each other. Iterating through both array when the smallest value is in that array. TILL YOU FINISH USING ONE ARRAY/CANNOT ITERATE FURTHER
33
How do you Divide the Array?
Divide it in approximately half
34
How do you Merge 2 Sorted Arrays?
Variable i & j we store the current position in a[-] & b[-] THEN: 1) Allocate temp array, for the result 2) if a[i] <= b[j], copy a[i] to tmp[i+j] and i++ POINTS i TO NEXT VALUE in a 3) Otherwise, copy b[j] to tmp[i+j] and j++ POINTS j TO NEXT VALUE in b REPEAT 2&3, till i or j reach the end of a[-] or b[-], then copy the rest of the other array a finished first then copy all elements of b into temp, OR b finished first then copy all elements of a into temp
35
What is a Non-Comparison Sort?
Must be something special about the data you're sorting SPECIAL CASE : Better than O(nlogn)
36
Idea of Binsort?
-Bins are queue data structure, which maintains the order that records are inserted into - Final Step: Concatenate the queues together in order to get single list of records
37
What is BINSORT?
Assigns records based on the key value of the record alone
38
Is Binsort Stable?
Yes, elements belong in the same bin are enqueued in the order that they appear in input Don't mess up input order of the items
39
Binsort complexity?
O(n) One pass through the input to fill the bins & One pass through the bins to create output list
40
How does Binsort work for dates?
USE a Multi-Phase Binsort - Binsort for one condition than another - Repeat for No. of conditions
41
What is Bucketsort
-Variant of Binsort - Scattered into buckets based on a range of numeric values or a set of categories {e.g - length/size of items}
42
What is Radix Sort?
- Multi-phase Binsort - Key sorted on in each phase is a different more significant base power of the integer key
43
How are Keys in Radix Sort Sorted?
KEYS ARE SORTED FIRST BY THE MOST SIGNIFICANT DIGIT, TO NEXT SIGNIFICANT, UNTIL UT REACHES LEAST SIGNIFICANT DIGIT
44
Complexity of Radix Sort?
O(kn) => where k is the no. of bits in a key can be reduced to O(kn/m) => groups m bits together & use 2^m bins => Increasing No. of bins improves the performance
45
What is General Complexity of Radix Sort?
O(n) => So long as n is not an extremely large number => Number require more space than int to hold it, need to look at overall complexity LARGER VALUE not held in single int COMPLEXITY is O(n*log(n))
46
What is Pigeonhole Sort?
Special case, when keys to be sorted are the numbers from 0 to n-1 Keys are typically just fields in records & requirements is to put the record in key value order, not just key values - Sorting record themselves, where each record holds a key value - Records have key values of 0 to n-1, then are sorted into random order SORTED by Pigeonhole so they are in order
47
How to do Pigeonhole sort?
Iterate through the input list directly assigning the input records to correct location in output array.
48
Complexity of Pigeonhole Sort?
O(n)
49
Idea of Piegonhole sort?
- Create a tmp array - For every item in list a, put the key value of Record i and put it in location index by key value - Copy array b into array a
50
Idea of INPLACE Piegonhole sort?
Avoid allocating extra array & copying - Iterate through the array, starting at first location & see a value that is there - The values are not in place SWAP IT with a value in it's correct place. Code for Swapping : Swap a[a[i]] and a[i] -If False increment i - Swap results in at least one key in its correct position - Once key is in correct position, never gets swapped
51
Time complexity for INPLACE Piegonhole Sort?
- At most n-1 swaps, so complexity is O(n)
52
What is Worst Case for INPLACE Piegonhole Sort
Every swap we het am extra key in the correct space
53
Idea of Merging?
1) Recursively split array into half until you get all elements in a single array 2) When u cannot split further merge right list with left list , Sort by comparing values and putting smallest value in first, Repeat till u get 2 sort both SIDES of Original Split left to mid and mid+1 to right 3) Compare values either side of the mid value staring at left for LHS of mid and mid+1 for RHS of the mid Value. Place smallest value into temp array and iterate that side by 1. Repeat until you reach the end of one RHS or LHS which is right for RHS and mid for LHS. Then add remaining values of the unfinished array to temp, while the tmpCount < = end of either side 4) Replace array a with sorted temp array
54
Complexity of Merge Sort
- Merging 2 arrays of length n_1 & n_2 is in O(n1+n2) - Every Recursive call splits the array in half, therefore each level require merging of O(n) e,g: START with n, then level 1 with spit in n in 1/2 level 2 will split n into 1/4 MERGING: Level 0 : O(n/2 + n/2 ) = O(n) Level 1 : O(2(n/4 + n/4 )) = O(n) If n = 2^k we have k = log_2(n) levels ==> O(nlog(n)) time Complexity for BEST/WORST/AVG This is Binary therefore we have log(n) levels log(n) LEVEL * O(n) Operations to merge
55
Is Merge sort Stable & why?
Yes, because splitting phase does not change the order of items So long as merging phase merges LHS with RHS in that Order & Take LHS value before RHS value if equal, then Doesn't change RELATIVE order IF DUPICATE VALUES MAKES SURE THAT RHS VALUE APPEARS AFTER THE LHS VALUES THEN IT IS STABLE
56
What does temp array affect in Merge?
Space Complexity NOT time
57
Principal of Quicksort?
1) Select an element of the array which we call pivot 2)Partition the array so that entries <= pivot are on LHS and entries > pivot are on RHS 3) Recursively sort the 2 partition
58
How to make Quicksort stable
Allow RHS of Pivot be equal to OR greater than pivot
59
Time Complexity of Quicksort
BEST CASE: O(nlog(n)) - Pivot is median in every iteration, then 2 partition have APPROX. n/2 elements WORST CASE: O(n^2) - Pivot is always the least element in ever iteration - Second partition contains all elements except the pivot, so n-1 - Consecutively second partition has: n-2,n-1,n-3,...,1 elements -BAD BALANCING/ UNBALANCING SPLIT AVG CASE: O(nlog(n)) - Depends on how pivot is chosen. - 25% many small entries or 25% large entries in all iterations, then partitioning happens log_4/3 n many times - QUICKER THAN MERGE
60
Principles of Partitioning array?
1) Choose a pivot in a 2) Allocate 2 temp arrays : tmpLE & tmpG 3) Store all elements >= pivot in tmpLE 4) Store all elements < pivot in tmpG 5) Copy arrays tmpLE & tmpG back to a return index of pivot in a TIME COMPLEXITY IS O(n)
61
Idea of Partitioning array - UNSTABLE INPLACE?
0) Takes array, left index , right index as Parameters 1) Choose pivot (pick index then find value by doing a[pIndex]) 2) Swap pivot with rightmost element in array 3) Create to pointer: leftPointer points to leftmost node; rightPointer points to right-1, rightmost non pivot node 4) While leftPointer <= rightPointer, check if a[leftPointer] is smaller than pivot , if so increment leftPointer. Then check if a[rightPointer] > than pivot, if so decrement rightPointer.DOES IN WHILE LOOP with leftPointer <= rightPointer FOR BOTH SEPARATLY. IF FALSE THEN SWAPS a[rightPointer] & a[leftPointer] . 5) If reaches end of all values checks if leftPointer < rightPointer, if so swaps a[leftPointer++] & a[rightPointer--] (Moves Pivot into mid position) 6) Returns leftPointer (PIVOT LOCATION)
62
Idea of Partitioning array - STABLE USING TEMP STORAGE?
0) Takes array, left index , right index as Parameters 1) Create new array b of size right-left+1 (MINMIAL CHANGE TO COMPLEXITY BUT SLOWER THAN UNSTABLE) 2) Choose pivot (pick index then find value by doing a[pIndex]) 3) Create 2 Pointers 1 for current array and another for temp array. i.e acount = left & bcount = 1 4) Iterate through a - Check if i is pivotindex if so put it int b[0] - check if it smaller then pivot OR equal pivot but smaller than pivot index, if so put it in a[account++] PUT IN A / CURRENT LAST POSTION IN A - Otherwise, put in b[bcount++] PUT IN B / CURRENT LAST POSITON IN B 5) Iterate through b and put all values into a starting from index account to Right 6) Return right-bcount+1 (PIVOT LOCATION)
63
4 Pivot Strategies?
- Middle entry - Median of Leftmost, Rightmost & middle Entries - Random Entry - Rightmost/Leftmost value
64
Idea of Middle Entry Pivot?
- Picks Middle value of array a - Works well with sorted/nearly sorted arrays - Not Sorted: can get both good/bad splits - DOESN'T GAURANTEE AVG PERFORMANCE FOR EVEY INPUT SEQUENCE, BUT HOLDS ON AVG
65
Idea of Rightmost/Leftmost Pivot value?
- Guarantees very poor performance if input is sorted or nearly sorted - Will give bad splits -O(n^2) DON'T USE
66
Idea Median of Leftmost, Rightmost & middle Entries Pivot VAL?
- Reduces probability of getting bad splits - Whichever value is in middle of these 3 values - DOESN'T GAURANTEE AVG PERFORMANCE FOR EVEY INPUT SEQUENCE, BUT HOLDS ON AVG
67
Idea a Random Entry as Pivot?
- 50% chance of getting a good pivot - Doesn't Guarantee find perfect pivot every single time - Low Probability of getting a sequence bad splits everytime - Guarantees AVG Peformance
68
Selection Sort Complexity?
Time: - Worse: O(n^2) - AVG: O(n^2) Space: - Worse: O(1) - AVG: O(1) Stability: NO
69
Heap Sort Complexity?
Time: - Worse: O(nlog(n)) - AVG: O(nlog(n)) Space: - Worse: O(1) - AVG: O(1) Stability: NO
70
Merge Sort Complexity?
Time: - Worse: O(nlog(n)) - AVG: O(nlog(n)) Space: - Worse: O(n) - AVG: O(n) Stability: YES
71
Quick Sort temp array Complexity?
Time: - Worse: O(nlog(n)) - AVG: O(n^2) Space: - Worse: O(n) - AVG: O(n) Stability: YES
72
Quick Sort INPLACE Complexity?
Time: - Worse: O(nlog(n)) - AVG: O(n^2) Space: - Worse: O(log n) - AVG: O(n) Stability: NO
73
If Picking Selection sort but what it to be stable what sort should you use instead?
INSERTION SORT
74
What should you do when you reach small region to sort (2- 16, MAX BETWEEN 8-16) in Merge & Quick sort?
Use Selection or alternative sort cause it is faster for smaller datasets SPEEDS UP TIMETAKEN
75
What Sorts should you use?
- Quick sort is significantly faster than any of the other sorts SORT to Guarantee Complexity of O(nlog(n)): -Use merge sort SORT when working with vey restricted Memory: - Use Heap Sort (Merge's Space Complexity = O(n))
76
Idea of Heap Sort
- Takes array & size of array as parameters - Heapify array - takes same parameters as sort - iterate through array and swap highest priority with end value {SWAP a[1] & a[j]}. - bubbleDown the tree use 1,a,j-1 as parameters -Each iteration decrement j
77
merge sort code help?
mergesort(a,n): does: - mergesort_run(array,left,right) mergesort_run: -checks if left
CS YEAR ONE
flashcards
Decks in class (16)
# Cards
Brainscape helps you reach your goals faster, through stronger study habits.
© 2026 Bold Learning Solutions. Terms and Conditions