is an in-place, unstable sorting algorithm that is

particularly useful when sorting arrays containing

elements with a small range of values.

it is an efficient sorting algorithm that minimizes the

number of memory writes. It works by placing each
element in its correct position and ensures that an
element is only written to its correct position once.
It is optimal in terms of the number of memory writes. It
minimizes the number of memory writes to sort (Each
value is either written zero times if it’s already in its
correct position or written one time to its correct
position.)

Cycle sort has a low memory footprint, as it sorts the

array in-place and does not require additional memory
for temporary variables or buffers.
Step 1: Count how many elements are smaller than 3 in the array (1 and 2),
so place 3 in index 2.

First cycle is done. The swapped element is 5.

Step 2: Now we count the elements that are less than 5. We have 4, in that
case we place element 5 in index 4.

Second cycle is done. The swapped element is 4.

Step 3: Now we count the number that are less than 4, there are 3, so move 4
to the 3rd index.

Third cycle done. The swapped element is 2.

Step 4: Now we count the elements that are less than 2. We have 1, in that
case we place element 2 in index 1.

Fourth cycle is done. The swapped element is 1.

Step 5: Finally, we know that there are no numbers that are less that 1 so we
place the element 1 to index 0 thus completed the sorting of the array using
cycle sort.

Fifth cycle is done, thus sorting the array

 DATA STRUCTURE AND ALGORITHM

QUICK SORT ALGORITHM

PRESENTED BY: RON JOSEPH R. ALCANTARA

 WHAT IS QUICK SORT ALGORITHM?

Quick Sort is a widely-used, efficient sorting algorithm based on the Divide and
Conquer paradigm. Invented by Tony Hoare in 1960, it is particularly appreciated
for its average-case time complexity of O(nlogn). Quick Sort operates by
selecting a pivot element, partitioning the array into two sub-arrays around the
pivot, and then recursively sorting these sub-arrays.
 KEY CONCEPTS OF QUICK SORT ALGORITHM?

Quick sort algorithm is a recursive algorithm

Quick sort = pivot (is one of them items in the array that meets the three following
conditions after its sorted.)

1.Correct position in final, sorted way

2.Items to the left are smaller
3.Items to the right are larger
HOW DOES QUICK SORT WORKS?
Example:

The first step in quick sort is to choose a pivot

In this example we take 3 as our pivot

We move the pivot to the ending array, to get it out of our way
Next step is we are going to look for two items
Lets swap the item form the left to the item from the right
We repeat the process, 5 is the item from left and 0 is item from right

Again, we swap 5 and 0

Item from left has a greater index than item from right
We swap item from left with our pivot

3, our pivot is now in our correct spot

Because quick sort is recursive, we repeat the process with the larger partition that
we made

We’ll choose 7 as our pivot and move it in the end

We repeat the same process
We repeat the same process
We repeat the same process
We now have 3 and 7 in their correct positions

Because Quict Sort is a recursion algorithm, we will repeat the same process
HOW TO CHOOSE THE PIVOT?
 HOW TO CHOOSE THE PIVOT?
A popular method is called the “median-of-three”

It is a method where we look at the first, middle, and last elements of the array

We sort them properly and choose the middle item as our pivot
PSEUDOCODE FOR QUICKSORT
CONCLUSION
 CONCLUSION
Quick Sort is an efficient and widely used algorithm with a well-balanced tradeoff
between complexity and performance. While Quick Sort is not stable and may have
limitations in scenarios requiring guaranteed efficiency for all input types, strategies
like random pivot selection or hybrid methods (e.g., Introsort) help mitigate these
drawbacks. Overall, Quick Sort remains one of the most widely used sorting
algorithms due to its balance of speed, memory efficiency, and implementation
simplicity.
SOURCE
 TAG SORT
Reymond Kent A. Montecillo

01
 Tagged Array Sorting
02
 Tagged Array
Sorting
• This is not a new sorting algorithm but an approach for avoiding the swapping of large objects
during sorting.
• It is especially useful when we need to maintain the original array intact while sorting.
• Sorting algorithms like Quick Sort or Bubble Sort are commonly used to sort array elements.
• Sometimes, it’s necessary to keep the original array unchanged and create a "tagged" array
that stores the correct position of each element after sorting.
• The "tagged" array allows accessing elements in sorted order without modifying the original
array.

03
 Why Use Tag Sort?
04
 Efficiency with Large Arrays:
• When working with large arrays of objects,
swapping the objects can be expensive,
especially with disk operations.
•
Reducing these costly swaps helps improve
performance.
How Tag Sort Helps:
• Tag Sort allows you to sort an integer array that
acts as a "tag" for the original objects.
• Instead of swapping the actual objects, only the
integers in the tag array are swapped.
• The original array remains unchanged, and the tag
array reflects the correct order of elements after
sorting.

05
 EXAMPLE #1

06
 EXAMPLE #2

07
08
This Sorting Technique is similar to the Selection Sort in
which we first find the smallest element called Bingo
Element, and then we repeatedly iterate the
elements of the array to get the correct positions of all
the elements. Similarly, find the next bingo element for
the next pass, and so on. Every distinct element is
considered a Bingo Element and called out in
increasing order.
Selection sort does one pass through the remaining items
for each item moved. Bingo sort does one pass for each
distinct value (not item) and moves every item with that
value to its final location
 In this sorting technique, each distinct element is considered a Bingo value.
And Bingo Values are called out in increasing order. During each pass, if the
array element is equal to Bingo element then it is shifted to its correct position.
Follow the below illustration for a better understanding. Let’s consider the

following array as an example: arr[] = [5, 4, 8, 5, 4, 8, 5, 4, 4, 4]

Step 1: Find the smallest value which is called a Bingo Element. Smallest element = 4
Step 2: Shift all the elements of the array to their correct position which is
equal to the Smallest element by swapping the position of Elements.

First Pass:

Second Pass:
Third Pass:

Fourth Pass:
 Fifth Pass:

Step 3: Similarly find the next Bingo Element (or smallest element) and shift
the elements to their correct position that are equal to Bingo Element. Next
Bingo Element = 5
Sixth Pass:
 Seventh Pass:

Step 3: Similarly find the next Bingo Element (or smallest element) and shift
the elements to their correct position that are equal to Bingo Element. Next
Bingo Element = 5
Eighth Pass:

Finally, Our array has been arranged in the increasing order as you can see
above
Strand Sort is a recursive, sorting algorithm that
builds sorted sublists (or "strands") from an input
list and then merges them together to form a
fully sorted list. It is most effective on data that
is already partially sorted.​
1. Create an empty result list.​
2. Repeatedly extract strands from the input list:​
• A strand is a subsequence of elements from
the input list that are in increasing order.​
• Remove the elements of the strand from the
original list.​
• Merge the strand into the result list.​
3. Continue until the input list is empty.
Suppose you have the list:​
[4, 2, 3, 1, 5, 8, 6, 7]​
First Strand: [4, 5, 8]​
Remaining list: [2, 3, 1, 6, 7]​
Second Strand: [2, 3, 6, 7]​
Remaining list: [1]​
Third Strand: [1]​
Finally, merge the strands together into the sorted list:​
[1, 2, 3, 4, 5, 6, 7, 8]​