Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit9480c34

Browse files
author
Eric Steen
committed
Radix sort
1 parent709fbf6 commit9480c34

File tree

8 files changed

+177
-10
lines changed

8 files changed

+177
-10
lines changed

‎ex‎

Lines changed: 0 additions & 9 deletions
This file was deleted.

‎python_algorithms/algorithms/search/bsearch.py‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -42,7 +42,7 @@ def binary_search_recursive(data, target, low, high):
4242
printbinary_search_iter(data,5)
4343
printbinary_search_recursive(data,5,0,len(data)-1)
4444

45-
# FOR INFINITESTREAMS
45+
#JUMP SEARCHFOR INFINITESTREAM
4646
# Search an infinite list of words in sorted order for an index corresponding to a word as input
4747
# given an infinite list ["apple", "banana", "cat", "dog", ...] we have a class A where A.get(2) # => "cat" write a function to return the index for the word given as input to the function like so:
4848
#
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
# The main function that sort the given string arr[] in
2+
# alphabetical order
3+
defcountSort(arr):
4+
5+
# The output character array that will have sorted arr
6+
output= [0foriinrange(len(arr))]
7+
8+
# Create a count array to store count of inidividul
9+
# characters and initialize count array as 0
10+
count= [0foriinrange(256)]
11+
12+
# For storing the resulting answer since the
13+
# string is immutable
14+
ans= [""for_inarr]
15+
16+
# Store count of each character
17+
foriinarr:
18+
count[ord(i)]+=1
19+
20+
# Change count[i] so that count[i] now contains actual
21+
# position of this character in output array
22+
foriinrange(256):
23+
count[i]+=count[i-1]
24+
25+
# Build the output character array
26+
foriinrange(len(arr)):
27+
output[count[ord(arr[i])]-1]=arr[i]
28+
count[ord(arr[i])]-=1
29+
30+
# Copy the output array to arr, so that arr now
31+
# contains sorted characters
32+
foriinrange(len(arr)):
33+
ans[i]=output[i]
34+
returnans
35+
36+
arr="geeksforgeeks"
37+
ans=countSort(arr)
38+
print("Sorted character array is % s"%("".join(ans)))
Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
defisort(arr):
2+
foriinxrange(1,len(arr)):
3+
j=i-1
4+
key=arr[i]
5+
6+
while (arr[j]>key)and (j>=0):
7+
arr[j+1]=arr[j]
8+
j-=1
9+
arr[j+1]=key
10+
returnarr
11+
12+
print(isort([3,4,1,3]))
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
# A function to do counting sort of arr[] according to
2+
# the digit represented by exp.
3+
4+
defcountingSort(arr,exp1):
5+
6+
n=len(arr)
7+
8+
# The output array elements that will have sorted arr
9+
output= [0]* (n)
10+
11+
# initialize count array as 0
12+
count= [0]* (10)
13+
14+
# Store count of occurrences in count[]
15+
foriinrange(0,n):
16+
index= (arr[i]/exp1)
17+
count[int(index%10)]+=1
18+
19+
# Change count[i] so that count[i] now contains actual
20+
# position of this digit in output array
21+
foriinrange(1,10):
22+
count[i]+=count[i-1]
23+
24+
# Build the output array
25+
i=n-1
26+
whilei>=0:
27+
index= (arr[i]/exp1)
28+
output[count[int(index%10)]-1]=arr[i]
29+
count[int(index%10)]-=1
30+
i-=1
31+
32+
# Copying the output array to arr[],
33+
# so that arr now contains sorted numbers
34+
i=0
35+
foriinrange(0,len(arr)):
36+
arr[i]=output[i]
37+
38+
defradixSort(arr):
39+
40+
# Find the maximum number to know number of digits
41+
max1=max(arr)
42+
43+
# Do counting sort for every digit. Note that instead
44+
# of passing digit number, exp is passed. exp is 10^i
45+
# where i is current digit number
46+
exp=1
47+
whilemax1/exp>0:
48+
countingSort(arr,exp)
49+
exp*=10
50+
51+
52+
arr= [170,45,75,90,802,24,2,66]
53+
54+
radixSort(arr)
55+
56+
foriinrange(len(arr)):
57+
print(arr[i])

‎python_algorithms/etc/csv.py‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
importcsv
2+
3+
withopen('rates.csv',newline='')ascsvfile:
4+
rates=csv.reader(csvfile,delimiter=' ',quotechar='|')
5+
forrowinrates:
6+
print(', '.join(row))
7+
8+
# to dict, preserves ordering
9+
withopen('names.csv',newline='')ascsvfile:
10+
reader=csv.DictReader(csvfile)
11+
forrowinreader:
12+
print(row['first_name'],row['last_name'])
Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
2+
defcan_find_zero(lst,i=0):
3+
4+
# is first elem 0?
5+
# if not move lft/rt according to value
6+
# is new value == 0?
7+
# if not continue process above until 0 found else False
8+
9+
found=False
10+
11+
whilelst[i]!=0andnotfound:
12+
elem=lst[i]
13+
ifelem==0:
14+
found=True
15+
else:
16+
found=recurse_elems(lst,i )
17+
18+
returnfound
19+
20+
defrecurse_elems(lst,i):
21+
found=False
22+
el=lst[i]
23+
lft=i-list[i]
24+
rt=i+lst[i]
25+
ifel==0:
26+
returnTrue
27+
else:
28+
iflft<0orrt>lst[len(lst)-1]:
29+
returnFalse
30+
found=recurse_elems(lst,lft)
31+
iffound:
32+
returnTrue
33+
found=recurse_elems(lst,rt)
34+
iffound:
35+
returnTrue
36+
37+
38+
returnfound
39+
40+
canFindZero([3,7,0,2,8,3,7,6])==True
41+
42+
43+
defshouldSave(userData):
44+
avail_bal=userData['accounts']['balance']['available']
45+
46+
transactions=userData['transactions']
47+
summ=0
48+
fortintransactions:
49+
amt=t['amount']
50+
summ+=amt
51+
52+
pct=summ/avail_bal
53+
ifavail_bal>=summ:
54+
returnTrue
55+
else:
56+
returnFalse

‎python_algorithms/etc/misc/spiral.py‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -64,6 +64,7 @@ def spiralCopy(inputMatrix):
6464
n=len(inputMatrix)
6565
m=len(inputMatrix[0])
6666

67+
# set initial processing boundary indexes
6768
topRow=0
6869
btmRow=n-1
6970
leftCol=0

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp