Question about a quicksort algorithm

Python Help
1

So here’s my issue, i hope this makes sense I’m terrible at explaining things
I don’t have any code to show for this all I’ve done is a few rough notes in my history copy that I relay all the important info from in this.

I’m creating a list of random ints, and making my own quicksort algorithm for it. My question is can i have a list of numbers, and each number has it’s own data attached to it. My point on this is to work out weather or not a number has been used as a pivot, because once it’s ben used as a pivot its in the right place in the list, and if there’s a number alone in between 2 pivots then it’s also in the right place

So if i have a list that looks like
42 17 79 55 33 91 68 10 26 83
It’ll be sorted like this (key is; [current pivot] (previous pivot) {between 2 pivots})
42 17 79 [55] 33 91 68 10 26 83
42 18 [33] 10 26 (55) 79 91 68 [83]
[17] 10 26 (33) {42} (55) [79] 68 (83) {91}
{10} (17) {26} (33) {42} (55) {68} (79) (83) {91}

so how would i represent the data how i did there with the different brackets (doesn’t necessarily have to be with brackets that’s just an example)? I’ve considered having a second list but you have to move arround that list too and it just gets very confusing

2

If you are implementing quicksort correctly, the original pivot does not appear in either of the sublists being recursivley sorted. Starting with

 42 17 79 55 33 91 68 10 26 83

you partition the list on 55 to get something like

42 17 26 10 33   55   68 91 79 83

55 is now out of consideration: you recursively sort 42 17 26 10 33 and 68 91 79 83, which leaves your whole list sorted.

3

As already noted, you don’t need or want to try anything like this for your current problem, because it is not useful. The way that quicksort works, you don’t need to track whether a number has been used as a pivot - because you don’t use the pivot in any of the recursive calls, you just stick it in place between the results of those recursive calls.

That said, you should still learn these techniques for the future. The general way that you “attach” data to some existing value, is to make your own data structure that contains the original value along with whatever is being attached. Sometimes you have a value that can already have more data attached to it (for example, if it were an instance of your own class, or a list or dict); but that doesn’t work for ints. So we fix that by just wrapping the value up in something where we can store extra data, and unwrap it later.

For a simple example, we could replace these integers with two-element lists, containing the original integer and a boolean flag:

[[42, False], [17, False], [79, False], [55, False], [33, False], [91, False], [68, False], [10, False], [26, False], [83, False]]

We can move the inner lists around as normal, and also replace False values with True when needed, and extract the ints afterward.