I was given the task to visualize Quicksort at university. I wrote the partition of the algorithm very small-stepped, so that I can visualize every single step well.
My array looks like this:
const [arr, setArr] = useState([
{number: 1, isSelectedFromLeftArrow: false, isSelectedFromRightArrow: false, isPivot: false, isSorted: false},
{number: 5, isSelectedFromLeftArrow: false, isSelectedFromRightArrow: false, isPivot: false, isSorted: false},
{number: 3, isSelectedFromLeftArrow: false, isSelectedFromRightArrow: false, isPivot: false, isSorted: false},
{number: 4, isSelectedFromLeftArrow: false, isSelectedFromRightArrow: false, isPivot: false, isSorted: false},
{number: 2, isSelectedFromLeftArrow: false, isSelectedFromRightArrow: false, isPivot: false, isSorted: false},
{number: 7, isSelectedFromLeftArrow: false, isSelectedFromRightArrow: false, isPivot: false, isSorted: false},
{number: 6, isSelectedFromLeftArrow: false, isSelectedFromRightArrow: false, isPivot: false, isSorted: false},
])
I added several attributes to each number to be able to see what is happening with the element later when I display it, so that I can color it afterwards.
My problem is now the following. The algorithm itself works and gives me the correct result in the console. However, the display of the bars does not change. Only when I go into the IDE, make a small change and the display changes to the finished result.
In the first step only the sorted element should be colored.
Here is the actual quicksort process:
const newTryQuickSort = async () => {
let stack = []
// Zu Beginn nur ein großes Array, welches sortiert werden soll. Von index 0 bis zum letzten Element
stack.push(0)
stack.push(arr.length - 1)
// while(stack[stack.length - 1] >= 0) {
for (let i = 0; i <= 3; i++) {
// Erste Element ist die linke Grenze und das zweite Element ist die rechte Grenze
let rightEnd = stack.pop()
let leftStart = stack.pop()
// Sortiere die erste Partition
const pivotIndex = await newPartition(leftStart, rightEnd)
console.log("Result from Partition: " + pivotIndex)
if (pivotIndex - 1 > leftStart) {
stack.push(leftStart)
stack.push(pivotIndex - 1)
}
if (pivotIndex + 1 < rightEnd) {
stack.push(pivotIndex + 1)
stack.push(rightEnd)
}
console.log('Stack: ')
console.log(stack)
console.log('______________________________________________________')
}
Here is the partitioning:
const newPartition = async (leftStart, rightEnd) => {
const pivotValue = arr[rightEnd].number
const pivotIndex = rightEnd
const left = leftStart
// Das pivot element ist das letzt Element, daher muss die Grenze bis eins vorher gehen
const right = rightEnd - 1
let pivotIsSorted = false
while (!pivotIsSorted) {
// Lass den Linken pfeil laufen
const leftArrowIndex = await checkFromLeft(left, right, pivotValue, pivotIndex)
console.log('leftArrowIndex: ' + leftArrowIndex)
// Wenn null rauskommt, gab es nur ein Element, welches dann sortiert ist.
if (leftArrowIndex === null) {
pivotIsSorted = true
return leftArrowIndex
}
// Überprüfen, ob null zurückkommt, da dann das Array bereits sortiert ist
//Lass den rechten Pfeil laufen
const rightArrowIndex = await checkFromRight(left, right, pivotValue, leftArrowIndex)
console.log('rightArrowIndex: ' + rightArrowIndex)
// Wenn beide ein Element gefunden haben, welches nicht passt und sie sich nicht getroffen haben,
// dann tausche sie, setzte leftStart und rightStart neu und beginne von vorne
if (leftArrowIndex !== rightArrowIndex) {
await swap(leftArrowIndex, rightArrowIndex, false)
leftStart = leftArrowIndex
rightEnd = rightArrowIndex
}
// Beide pfeile haben sich getroffen (indexLeft === indexRight)
// Tausche die stelle, wo sich die Pfeile getroffen haben mit dem pivot und gebe das/die neue/neuen subarray/s zurück
if (leftArrowIndex === rightArrowIndex) {
await swap(leftArrowIndex, pivotIndex, true)
pivotIsSorted = true
// Das Pivot element liegt nach dem swapt an der Stelle von leftArrowIndex
return leftArrowIndex
}
}
}
const checkFromLeft = async (start, end, pivot, pivotIndex) => {
console.log('checkFromLeft: start, end, pivot')
console.log(start, end, pivot)
// Wenn das subarray, welches sortiert werden soll nur 1 Element groß ist, ist es fertig sortiert
if (start === end) {
// Vertausche die beiden an der gleichen Stelle, um es als sortiert zu setzten
console.log('Im hear')
await swap(start, end, true)
// Gebe 'null' zurück, um zu sagen, dass das subarray nur ein element groß ist
return null
}
// Ansonsten gehe von links nach rechts alle Elemente durch und suche nach einem Element, welches größer ist als das pivot
for (let i = start; i <= pivotIndex; i++) {
if (arr[i].number >= pivot) return i
// Trifft auf den rechten pfeil, welcher noch nicht losgelaufen ist - VORHER
// Trifft auf das Pivot, somit steht es an der richtigen stelle - NACHHER
if (i === pivotIndex) return i
}
}
const checkFromRight = (start, end, pivot, positionOfLeftArrow) => {
for (let i = end; i >= start; i--) {
// Wenn er an der gleichen Stelle ankommt oder der linke schon am Pivot ist, wie der linke Pfeil, gibt er nicht seine, sondern die
// Position des Linken pfeils zurück (da der linke Pfeil ja auch schon weiter sein kann, als der Rechte)
if (i <= positionOfLeftArrow) {
return positionOfLeftArrow
}
// Wenn er ein Element gefunden hat, was kleiner als das pivot ist, gibt er es zurück
if (arr[i].number <= pivot) {
return i
}
}
}
Here is the swapping of the two elements:
const swap = async (left, rightOrPivot, isPivot = false) => {
setArr((prevArr) => {
// Tausche beide Werte aus
const oldLeft = prevArr[left]
prevArr[left] = prevArr[rightOrPivot]
prevArr[rightOrPivot] = oldLeft
console.log('NewArray after swap: ')
console.log(prevArr)
// Wenn das Pivot verschoben wurde, so ist es nun an seiner Finalen Position
if (isPivot) {
prevArr[left].isPivot = false
prevArr[left].isSorted = true
}
return prevArr
})
await sleep(1000)
return true
}
const sleep = (ms) => {
return new Promise(resolve => setTimeout(resolve, ms))
}
I use a useEffect to output the array whenever it changes. It is also strange that the array is already sorted at the first output.
useEffect(() => {
console.log("Arr: ")
console.log(arr)
}, [arr])
Here is a screenshot of the console:
Image of the visualization and console
I hope you can help me there.
