<jupyter_start><jupyter_text>Sorting - selection sort & insertion have a complexity of O(n^2)- O(n^2) is not feasible for computations more than 5000So to tackle all these we use other sortings, that are with less complexity...  Merge sort-- Here we divide the list into 2 and sort then individually- Then we pick the elements from the those individually, in order that we want- if ascending we pick smaller from both and then check in both for next(for decending vice versa)1) divide list into half, then those halfs into halves until they become 1 element2) we start the reverse order by combining 1 elements -> 2, then and so on..  Divide & conquer- Breakup problem into disjoint parts- solve separately & combine efficiently<jupyter_code>def merge_sort(A,B):
  c = []
  m = len(A)
  n = len(B)
  i = 0
  j = 0
  # (i,j) = (0,0) # current A,B positions

## merging
  while i+j < m+n:
    if i == m:
       # A is Empty
      c.append(B[j])
      j += 1  
    elif j == n:
      c.append(A[i])
      i += 1
    elif A[i] <= B[j]:  # head of A is smaller
      c.append(A[i])
      i += 1
    elif A[i] > B[j]:
      c.append(B[j])
      j += 1
  return c               
a = [23,12,43,5,21,534]
b = [43,2,54,64,4]
merge_sort(a,b)
def msort(A,left,right):
  if right - left <= 1:
    return (A[left:right])

  if right - left > 1:
    mid = (left+right) // 2
    L = msort(A,left,mid)
    R = msort(A,mid,right)

    return (merge_sort(L,R))  
msort(a,0,len(a))<jupyter_output><empty_output><jupyter_text>- The recursive not for 1 element but for half the list, so here  n log(n)  Quick sort- mergesort requires more space for performing- takes recursive which takes more time1. Divide & conquer without merging- find median and arrange left & right- recursively sort left & right- A now sorted- T(n) = 2T(n/2)+n = O(n log n)above the problem is to find median, so to address this, we pick a pivot<jupyter_code>def quicksort(A,l,r):
  if r-l <= 1: #base case
    return ()

  yellow = l+1
# pivot
  for green in range(l+1,r):
    if A[green] <= A[l]:
      (A[yellow],A[green])=(A[green],A[yellow])
      yellow = yellow + 1

  # moving pivot 
  (A[l],A[yellow-1]) = (A[yellow-1],A[l])

  quicksort(A,l,yellow-1)
  quicksort(A,yellow,r)<jupyter_output><empty_output><jupyter_text>QUick sort Analysis- choose a pivot usually first value of array- partition A into lower and upper parts with respect to pivot- move pivot b/w lower & upper- recursively sort two partitions 1. pivot is either minimum or max - - **worst case**one partition is empty.other has size n-1.T(n) = T(n-2)+(n-1)+n = O(n2). Already sorted is the worst case for quiuck sort.but Average case is O(n log n) *   QUICK sort is very fast*   default sort for many spread sheet & programming languages* randomizing list will give very fast result  Tuplestuples is a sequence but immutable one<jupyter_code>a = ()
type(a)
a[1]=3 # tuples are immutable
a[0] # we get a slice from tuple as it dont change orginal list<jupyter_output><empty_output><jupyter_text>Generlizing lists- The elements in a list are sequenced in a order where elements are assigned to a index<jupyter_code>a = [1,2,4,5,6,7]
for i in range(len(a)):
  print(i,end=" ")<jupyter_output>0 1 2 3 4 5<jupyter_text>DictionariesDictionaries are mutable, but keys are not mutable<jupyter_code>new = {} # empty dict declaration, should assign a dictionary before use
new['a'] = 1<jupyter_output><empty_output><jupyter_text>- The can be int, float, string, tuple, bool but not list, dictionary<jupyter_code>new['test']['kohli']=23 # test is not declared
new['test']={}
new
new['test']['kohli']=23
new
new.keys()
type(new.keys()) # not a list, a different data structure<jupyter_output><empty_output><jupyter_text>- keys are not in order, we can use sorted for this, where it dont change orginal<jupyter_code>type(new.values())
new_dict = {1:'a',3:'ads',4:'hed',5:'ajf'}
new_dict.keys()
sorted(new_dict.keys()) # this helps in preserving key order
total={}
score={}
for n in ['kohli','Dhawan','Yuvraj']:
  total[n] = 0
  for match in score.keys():
    if n in score[match].keys():
      total[n] = total[n]+score[match][n]
total
score<jupyter_output><empty_output><jupyter_text>Function defination<jupyter_code>def quicksort(a, l =10,r=len(a)) # this wont work, because r is not static
def quick(a,b,c=19,d=22) # this works because the inputs are static, these should happen at time of defination
quick(2,3)  --> interprets as quick(2,3,19,22)
quick(3,5,6) ---> interprets as quick(3,5,6,22)<jupyter_output><empty_output><jupyter_text>-> order os argument is important<jupyter_code>if condition:
  def g(a,r,d):
else:
  def g(a,d,r)    
def f(a):

g = f
# so here we can use
g(a)<jupyter_output><empty_output><jupyter_text>- Function definations behave like other assignments of values to names- can reassign a new defination, using conditionally- can pass function name to other functions  List Comprehension- Map applies function to each element, map(f,l) applies f to each element of l.- map(f,l) is not a list, but a map object- to get as list, list(map(f,l)) to get a list<jupyter_code>def subl(new,lis):
  sublist = []
  for x in lis:
    if new(x):
      sublist.append(x)

  return sublist<jupyter_output><empty_output><jupyter_text>OR<jupyter_code>filter(new,lis)  # do same as it to element that support the new property
list(map(square,filter(iseven,range(100))))

def square(x):
  return x**2

def iseven(x):
  return x%2 == 0

[square(x) for i in range(100) if iseven(x)] # square(x) - map
# for - generator
# iseven - filter<jupyter_output><empty_output><jupyter_text>-> Inner generators are dependent on outer generators<jupyter_code># pythogorous triples

[(x,y,z) for x in range(100) for y in range(100) for z in range(100) if x*x+y*y==z*z]

[(x,y,z) for x in range(100) for y in range(x,100) for z in range(y,100) if x*x+y*y==z*z]
[[0 for i in range(3)] for j in range(4)]
[[(0) for i in range(3)] for j in range(4)]
[[i for i in range(3)] for j in range(4)]<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12809026049444167, 'fraction_numerical': 0.023560643769703002, 'mean_word_length': 4.273840769903762, 'pattern_counts': {'":': 0, '<': 53, '<?xml version=': 0, '>': 55, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '12', 'dir': 'jupyter-structured-clean-dedup', 'id': '355241', 'license': 'MIT', 'n_tokens_mistral': 2256, 'n_tokens_neox': 2133, 'n_words': 742, 'path': 'Jayaprakash/Day_1/sorting,tuples,dictionaries,passingfunc&LC.ipynb', 'repo_name': 'Jayjake1/100-Days-of-Code', 'size': '6027'}