<jupyter_start><jupyter_text>Quick Sort<jupyter_code>import random
a = [6, 2, 4, 2, 1, 9, 8, 5, 1, 1] 
n=len(a)
    
def partition(a,low,high): 
    i = (low-1)
    pivot = a[high]
    for j in range(low , high): 
        if   a[j] <= pivot: 
            i = i+1 
            a[i],a[j] = a[j],a[i] 
  
    a[i+1],a[high] = a[high],a[i+1] 
    return(i+1) 

def Quick_Sort(a,low,high): 
    if low < high:
        p = partition(a,low,high) 
        Quick_Sort(a, low, p-1) 
        Quick_Sort(a, p+1, high) 
        

Quick_Sort(a,0,n-1)

print ("Sorted array is:") 
for i in range(len(a)): 
    print (a[i], end=" ")<jupyter_output>Sorted array is:
1 1 1 2 2 4 5 6 8 9<jupyter_text>Stable check - Quick Sort<jupyter_code>a = [2, 2, 4, 2, 1, 8, 8, 5, 1, 1] 
n=len(a)

traversed = []
freq_us=[0,0,0,0,0,0,0,0,0,0]   #initialising frequency list with 0 values

#-----
#frequency-check
for i in range(0, 10):   #traversing the original array
    temp = a[i]   
    traversed.append(temp)   #adding each visited element to traversed
    count=0   
    for j in range(len(traversed)):
        if temp==traversed[j]:
            count=count+1   #checking count of the visited element in traversed
    freq_us[i]=count   #designating appearance frequency of element to its frequency position

print("Unsorted array and frequency of elements:")
print(a)
print(freq_us)

freq_s=freq_us.copy()   #making a copy of the unsorted frequency list to frequency list with sorted values

    
def partition(a,low,high): 
    i = (low-1)
    pivot = a[high]
    for j in range(low , high): 
        if   a[j] <= pivot: 
            i = i+1 
            a[i],a[j] = a[j],a[i] 
            freq_s[i], freq_s[j] = freq_s[j], freq_s[i]
  
    a[i+1],a[high] = a[high],a[i+1] 
    freq_s[i+1],freq_s[high] = freq_s[high], freq_s[i+1]
    return(i+1) 

def Quick_Sort(a,low,high): 
    if low < high:
        p = partition(a,low,high) 
        Quick_Sort(a, low, p-1) 
        Quick_Sort(a, p+1, high) 
        

Quick_Sort(a,0,n-1)

print()
print ("Sorted array is:") 
print(a)
print(freq_s)<jupyter_output>Unsorted array and frequency of elements:
[2, 2, 4, 2, 1, 8, 8, 5, 1, 1]
[1, 2, 1, 3, 1, 1, 2, 1, 2, 3]

Sorted array is:
[1, 1, 1, 2, 2, 2, 4, 5, 8, 8]
[1, 2, 3, 3, 1, 2, 1, 1, 1, 2]<jupyter_text>Stability-check in-code implemented<jupyter_code>a = [1, 7, 4, 2, 1, 8, 8, 5, 7, 1] 
n=len(a)

traversed = []
freq_us=[0,0,0,0,0,0,0,0,0,0]   #initialising frequency list with 0 values

#-------------------
#frequency-check
#-------------------

for i in range(0, 10):   #traversing the original array
    temp = a[i]   
    traversed.append(temp)   #adding each visited element to traversed
    count=0   
    for j in range(len(traversed)):
        if temp==traversed[j]:
            count=count+1   #checking count of the visited element in traversed
    freq_us[i]=count   #designating appearance frequency of element to its frequency position

print("Unsorted array and frequency of elements:")
print(a)
print(freq_us)

freq_s=freq_us.copy()   #making a copy of the unsorted frequency list to frequency list with sorted values

#-----------
#Quick-sort
#-----------
    
def partition(a,low,high): 
    i = (low-1)
    pivot = a[high]
    for j in range(low , high): 
        if   a[j] <= pivot: 
            i = i+1 
            a[i],a[j] = a[j],a[i] 
            freq_s[i], freq_s[j] = freq_s[j], freq_s[i]
  
    a[i+1],a[high] = a[high],a[i+1] 
    freq_s[i+1],freq_s[high] = freq_s[high], freq_s[i+1]
    return(i+1) 

def Quick_Sort(a,low,high): 
    if low < high:
        p = partition(a,low,high) 
        Quick_Sort(a, low, p-1) 
        Quick_Sort(a, p+1, high) 
        

Quick_Sort(a,0,n-1)

print()
print ("Sorted array is:") 
print(a)
print(freq_s)

#---------------------
#stability-check now
#---------------------

t=[]
main_flag=0   #counts the number of times frequencies have deviated from ascending order

for i in range(len(a)-1):   #traversing the length of the lsit-1
    key=a[i]
    freq_s_temp=[]   #temp list for storing frequencies of each unique sorted-list-element
    t.append(key)   #adding each key to the list t that contains each element being traversed
    if a[i]==a[i+1]:   #checking for occurrence of same element in the sorted list
        count=0   
        for k in range(len(t)):   
            if key==t[k]:   #checking if traversed list contains key
                count=count+1   
        if count==1:   #this means it has been visited for the first time, more than 1 means we have already check frequency of this value         
            for j in range(i, len(a)):
                if key==a[j]:
                    freq_s_temp.append(freq_s[j])   #creating sub_list of each unique sorted-list-element
                                    
                desc=0   #checking for ascending order in each sub_list
                for m in range(len(freq_s_temp)-1):
                    if freq_s_temp[m]>freq_s_temp[m+1]:
                        desc=desc+1
                if desc!=0:   #if any frequency-sub-list has the elements in descending order -> unstability
                    main_flag=main_flag+1

print()
if main_flag==0:   #all frequency sub-lists are in ascending order
    print("Stable")
else:
    print("Unstable")<jupyter_output>Unsorted array and frequency of elements:
[1, 7, 4, 2, 1, 8, 8, 5, 7, 1]
[1, 1, 1, 1, 2, 1, 2, 1, 2, 3]

Sorted array is:
[1, 1, 1, 2, 4, 5, 7, 7, 8, 8]
[1, 2, 3, 1, 1, 1, 2, 1, 2, 1]

Unstable<jupyter_text>Quick sort stability-check with user input<jupyter_code>a = []
freq_us = []
  

#-----------
#user input
#-----------

num_of_ele = int(input("Enter number of elements : ")) 
 
for i in range(0, num_of_ele): 
    element = int(input())
    initial_freq=0
    a.append(element) # adding the element
    freq_us.append(initial_freq)

#a = [1, 7, 4, 2, 1, 8, 8, 5, 7, 1] 
#freq_us=[0,0,0,0,0,0,0,0,0,0]   #initialising frequency list with 0 values

traversed = []
n=len(a)


#-------------------
#frequency-check
#-------------------

for i in range(0, 10):   #traversing the original array
    temp = a[i]   
    traversed.append(temp)   #adding each visited element to traversed
    count=0   
    for j in range(len(traversed)):
        if temp==traversed[j]:
            count=count+1   #checking count of the visited element in traversed
    freq_us[i]=count   #designating appearance frequency of element to its frequency position

print("Unsorted array and frequency of elements:")
print(a)
print(freq_us)

freq_s=freq_us.copy()   #making a copy of the unsorted frequency list to frequency list with sorted values

#-----------
#Quick-sort
#-----------
    
def partition(a,low,high): 
    i = (low-1)
    pivot = a[high]
    for j in range(low , high): 
        if   a[j] <= pivot: 
            i = i+1 
            a[i],a[j] = a[j],a[i] 
            freq_s[i], freq_s[j] = freq_s[j], freq_s[i]
  
    a[i+1],a[high] = a[high],a[i+1] 
    freq_s[i+1],freq_s[high] = freq_s[high], freq_s[i+1]
    return(i+1) 

def Quick_Sort(a,low,high): 
    if low < high:
        p = partition(a,low,high) 
        Quick_Sort(a, low, p-1) 
        Quick_Sort(a, p+1, high) 
        

Quick_Sort(a,0,n-1)

print()
print ("Sorted array is:") 
print(a)
print(freq_s)

#---------------------
#stability-check now
#---------------------

t=[]
main_flag=0   #counts the number of times frequencies have deviated from ascending order

for i in range(len(a)-1):   #traversing the length of the lsit-1
    key=a[i]
    freq_s_temp=[]   #temp list for storing frequencies of each unique sorted-list-element
    t.append(key)   #adding each key to the list t that contains each element being traversed
    if a[i]==a[i+1]:   #checking for occurrence of same element in the sorted list
        count=0   
        for k in range(len(t)):   
            if key==t[k]:   #checking if traversed list contains key
                count=count+1   
        if count==1:   #this means it has been visited for the first time, more than 1 means we have already check frequency of this value         
            for j in range(i, len(a)):
                if key==a[j]:
                    freq_s_temp.append(freq_s[j])   #creating sub_list of each unique sorted-list-element
                                    
                desc=0   #checking for ascending order in each sub_list
                for m in range(len(freq_s_temp)-1):
                    if freq_s_temp[m]>freq_s_temp[m+1]:
                        desc=desc+1
                if desc!=0:   #if any frequency-sub-list has the elements in descending order -> unstability
                    main_flag=main_flag+1

print()
if main_flag==0:   #all frequency sub-lists are in ascending order
    print("Stable")
else:
    print("Unstable")<jupyter_output>Enter number of elements : 10
1
7
4
2
1
8
8
5
7
1
Unsorted array and frequency of elements:
[1, 7, 4, 2, 1, 8, 8, 5, 7, 1]
[1, 1, 1, 1, 2, 1, 2, 1, 2, 3]

Sorted array is:
[1, 1, 1, 2, 4, 5, 7, 7, 8, 8]
[1, 2, 3, 1, 1, 1, 2, 1, 2, 1]

Unstable<jupyter_text>Stability check for quick sort on randomly generated and populated lists for 1000000 times<jupyter_code>def quick_sort_is_stable():

    a = []
    freq_us = []
  

    #-----------
    #user input
    #-----------

    a = []
    freq_us = []

    num_of_ele=random.randrange(10, 30)
    #print("Number of elements is ", num_of_ele)
    largest = int(num_of_ele/2)

    for i in range(0, num_of_ele):
        element = random.randrange(1, largest)
        initial_freq=0
        a.append(element)
        freq_us.append(initial_freq)
    
    #print(a)
    #print(freq_us)
    #print()
    traversed = []
    n=len(a)


    #-------------------
    #frequency-check
    #-------------------

    for i in range(0, 10):   #traversing the original array
        temp = a[i]   
        traversed.append(temp)   #adding each visited element to traversed
        count=0   
        for j in range(len(traversed)):
            if temp==traversed[j]:
                count=count+1   #checking count of the visited element in traversed
        freq_us[i]=count   #designating appearance frequency of element to its frequency position

    #print("Unsorted array and frequency of elements:")
    #print(a)
    #print(freq_us)

    freq_s=freq_us.copy()   #making a copy of the unsorted frequency list to frequency list with sorted values

    #-----------
    #Quick-sort
    #-----------
    
    def partition(a,low,high): 
        i = (low-1)
        pivot = a[high]
        for j in range(low , high): 
            if   a[j] <= pivot: 
                i = i+1 
                a[i],a[j] = a[j],a[i] 
                freq_s[i], freq_s[j] = freq_s[j], freq_s[i]
  
        a[i+1],a[high] = a[high],a[i+1] 
        freq_s[i+1],freq_s[high] = freq_s[high], freq_s[i+1]
        return(i+1) 

    def Quick_Sort(a,low,high): 
        if low < high:
            p = partition(a,low,high) 
            Quick_Sort(a, low, p-1) 
            Quick_Sort(a, p+1, high) 
        

    Quick_Sort(a,0,n-1)

    #print()
    #print ("Sorted array is:") 
    #print(a)
    #print(freq_s)

    #---------------------
    #stability-check now
    #---------------------

    t=[]
    main_flag=0   #counts the number of times frequencies have deviated from ascending order

    for i in range(len(a)-1):   #traversing the length of the lsit-1
        key=a[i]
        freq_s_temp=[]   #temp list for storing frequencies of each unique sorted-list-element
        t.append(key)   #adding each key to the list t that contains each element being traversed
        if a[i]==a[i+1]:   #checking for occurrence of same element in the sorted list
            count=0   
            for k in range(len(t)):   
                if key==t[k]:   #checking if traversed list contains key
                    count=count+1   
            if count==1:   #this means it has been visited for the first time, more than 1 means we have already check frequency of this value         
                for j in range(i, len(a)):
                    if key==a[j]:
                        freq_s_temp.append(freq_s[j])   #creating sub_list of each unique sorted-list-element
                                    
                    desc=0   #checking for ascending order in each sub_list
                    for m in range(len(freq_s_temp)-1):
                        if freq_s_temp[m]>freq_s_temp[m+1]:
                            desc=desc+1
                    if desc!=0:   #if any frequency-sub-list has the elements in descending order -> unstability
                        main_flag=main_flag+1

    #print()
    if main_flag==0:   #all frequency sub-lists are in ascending order
        return 1   #this means stable
    else:
        return 0   #this means unstable
    

# function ends here

#----------

    
# to check time taken to run the code for 1,000,000 randomly generated and populated lists
import time
start_time = time.time()


result_list=[]

for x in range(1000000):   #Running the stability check for insertion sort on randomly generated and populated lists for x times
    #insertion_sort_is_stable()
    result = int(quick_sort_is_stable())
    result_list.append(result)
    
final_count=0
length = len(result_list)

for y in range(length):
    if result_list[y]==0:    # that is, if there is any instance of unstability
        final_count=final_count+1

if final_count==0:
    print("Quick sort is fully Stable")
else:
    print("Quick sort has Unstable instances")
    

#--------


print("--- %s seconds ---" % (time.time() - start_time))<jupyter_output>Quick sort has Unstable instances
--- 105.26054096221924 seconds ---
{'fraction_non_alphanumeric': 0.14266862170087977, 'fraction_numerical': 0.02837243401759531, 'mean_word_length': 2.144536652835408, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '365701', 'license': 'MIT', 'n_tokens_mistral': 5089, 'n_tokens_neox': 4666, 'n_words': 1403, 'path': 'Stable-Sort-Check-for-Quick-Sort.ipynb', 'repo_name': 'Not-A-Builder/uni-lab', 'size': '13640'}